BS 2

Der Compiler erzeugt aus jeder z.B. C-Datei (genauer aus jedem Quell-Modul) eine Objekt-Datei. Der Linker erzeugt aus den Objekt-Dateien ein Lademodul in dem alle Adressen sich auf die Anfangsadresse Null beziehen. Das Lademodul wird ohne Neuberechnung der Adressen in den Hauptspeicher (durch den Loader) an einer durch die Hauptspei-cherverwaltung des Betriebssystems frei wählbaren Stelle platziert  bzw. eingelagert.

Damit der Prozesswechsel ohne Schwierigkeiten funktioniert, werden für jeden bereiten oder blockierten Prozess die Inhalte des Befehlszählers und der übrigen Register zum Zeitpunkt einer Unterbrechung im (bzw. mittels des) Prozess-Kontrollblock gesichert. Ziel der Betriebssystem-Hauptspeicherverwaltung ist es den Prozessen Hauptspeicher zuzu-weisen und die Inhalte der zugewiesenen Hauptspeicherbereiche auch in diesen Wartezuständen zu erhalten. Eine wesentliche Aufgabe der Hauptspeicheverwaltung ist ferner die dynamische Allokation bzw. Hauptspeicherzuweisung bei der Einlagerung von Programmen bzw. von deren Lademodulen vom Sekundärspeicher (z.B. Festplatte).

Objektmodule verwenden symbolische Adressen; sozusagen die Adressen vor dem Linken. Was ist eine physische (absolute) Adresse?

Eine Adresse auf dem Adressbus welche auf eine Speicherstelle im Hauptspeicher verweist.

Eine logische Adresse ist ein (z.B. im Speicheradressregister stehender) Verweis auf eine physische Speicherstelle. Die logische Adresse existiert auch unabhängig von der aktuellen Laufzeit-Belegung des korrespondierenden physischen Speichers (Bsp.: page fault bei Auslagerung). Ein Prozess arbeitet nur mit (bzw. kennt nur) logischen Adressen statt physischen Adressen; d.h. das zugrundeliegende Programm wurde bezüglich des logischen (relativen) Adressraumes gebunden (gelinkt). Die logischen Adressen werden erst während der Prozesslaufzeit zum Zugriffszeitpunkt auf den Bus bzw. auf den Hauptspeicher via Hardware MMU (Memory Management Unit) auf die physischen Hauptspeicheradressen abgebildet bzw. umgerechnet.

Die Menge der logischen Adressen die der Prozess verwendet (durch Verwendung von Segmentierung kann der Prozess ggf. mehrere getrennte logische Adressräume besitzen z.B.: RAM-Daten-, Prozesstapel-, Programm- und Konstanz-Daten-Segment).

Die Programme können unabhängig von der Kenntnis der späteren physikalischen Lage im Hauptspeicher erstellt und gebunden (gelinkt) werden. Der binäre Programm-Code ist also relokierbar, was für die dynamische Allokierung notwendig ist. Da die Adress-abbildung (von logisch/virtuell nach physisch) zur Prozesslaufzeit z.B. über einen Hardware-Adressaddierer mit Basisregister in der MMU geschieht, kann durch zusätzlichen HW-Aufwand in der MMU z.B. mittels des Grenzregisters ein (Segment-) Speicherschutz gleich mit realisiert werden. Mehrere Prozesse können sich knappen physikalischen Speicher (auf Kosten von Aus- und Einlagerungszeit) teilen.

Die Verwendung mehrerer logischer Adressräume in einem Programm/Prozess anstatt nur eines logischen Adressraumes (bzw. bei x86 Segmentierungs + Paging MMUs: Die Aufteilung eines logischen/virtuellen Prozess-Adressraumes (sog. „linear address“) in mehrere logische Adressräume mittels Segmentierung bzw. mittels vorgeschalteter Segmentierungs-MMU-HW). Die Segmente eines Prozesses müssen nicht unbedingt physisch im Hauptspeicher hintereinander liegen, jedoch sind die Adressen innerhalb eines jeden Segments sowohl logisch als auch physisch zusammenhängend. Der Nachteil bei der Segmentierung (ohne „linear adress“ MMUs) ist die externe Fragmentierung des physischen Hauptspeichers. (Jedoch speziell für x86 „linear address“-MMUs: Da jedes Prozess-Segment einen eigenen logischen Adressraum beginnend von Adresse 0 hat, gibt es hier weniger Kollisionen falls ein Programm/Prozess-Block wächst. Des weiteren sind die dabei entstehenden Speicherlöcher (durch externe Fragmentierung) im virtuellen „linear adress“ Adressraum i.a. nicht störend, weil ja noch das Paging folgt.)  Zur Segment-Selektion werden i.a. die höherwertigsten Adressbits der logischen/virtuellen Adresse bzw. des Speicheradressregisters verwendet.

Hierbei wird der logische Adressraum eines Prozesses (bzw. seine Segment-Adressräume jeweils) auf einen zusammenhängenden physikalischen Speicherbereich abgebildet. Dazu müssen Programm-Code und ggf. Daten relokierbar gebunden (gelinkt) sein. Beim Laden wird dem Prozess ein Hauptspeicherbereich vom Langzeit-Scheduler mittels einer Allokierungs-Strategie (z.B. first fit, best fit) zugewiesen. Ein auf einen Sekundärspeicher (z.B. Festplatte) ausgelagerter Prozess muß, bevor er „rechnend“ werden kann, wieder in den Hauptspeicher eingelagert werden (sog. swapping). Diese erfolgt nicht notwen-digerweise in denselben physischen Speicherbereich im dem der Prozess vor der Aus-lagerung stand. Sind die zusammenhängenden zugewiesenen physischen Prozess-Adressräume (bzw. Segment-Adressräume) unterschiedlich groß, dann entstehen durch das „swapping“ mit der Zeit zwangsläufig ungenutzte Speicherlöcher außerhalb dieser Segmente. Diesen Effekt nennt man externe Fragmentierung (externen Verschnitt). Durch aufwendige Verschiebung kann man die physischen zusammenhängenden Adressräume wieder nahtlos aneinanderfügen. Dieses Aufräumen bei dynamischer Allokierung nennt man Kompaktifizierung.

Das „+“ sorgt für die Abbildung

von logisch  nach  physisch.

Das „<“ sorgt zusammen mit

dem „+“ für den Speicherschutz.

Der physische Speicher wird statisch in gleich große aneinander liegender Blöcke, sog.  Seitenrahmen (frames) aufgeteilt. Dadurch entfällt hier das Problem der externen Hauptspeicher-Fragmentierung. Ungenutzten Speicher innerhalb eines jeweils „letzten“ Blocks, sog. interne Fragmentierung kann es natürlich nach wie vor geben (durchschnittlich eine halbe Blockgröße im jeweils letzten Block) (Im Gegensatz zur Segmentierung besitzt jeder Prozess beim Paging nur einen logischen Adressraum so daß logisch unterschiedliche Blöcke beim Wachsen im logischen/virtuellen Adressraum miteinander kollidieren können). Der logische Adressraum ist ebenfalls in gleich große „Seiten“ (pages) aufgeteilt und über eine (ggf. mehrstufige) Seitentabelle werden z.B. 4k-Worte große logische Seiten-Adressbereiche jeweils auf gleichgroße physische Rahmen-Adressbereiche abgebildet. Dabei werden aus Effizienzgründen z.B. die niederwertigen 12 logischen Adress-Offset-Bits (=4k) direkt auf die 12 niederwertigen physischen Adress-Offset-Bits abgebildet, wodurch sowohl logische Seiten-Adressbereiche als auch physische Seitenrahmen-Adressblöcke gleich (z.B. auf 4k-Grenzen) ausgerichtet werden. Die Bits einer logischen Adresse setzen sich somit aus Seitennummer und Offset zusammen und die Bits einer physischen Adresse aus Seitenrahmennummer und Offset. Ein Index in die Seitentabelle ist eine Seitennummer und ein Eintrag in der Seitentabelle ist eine Seitenrahmennummer. Die Seitentabelle selbst darf nicht ausgelagert werden (zumindest nicht solange sie nur einstufig ist).

Man verwendet einen Adress-Cache (Translation Lookaside Buffer) der allerdings bei jedem Prozesswechsel „geflusht“ werden muß.

Annahme Zugriff HS:100ns, Cache:20ns: 80% Treffer: 0,8 *120ns + 0,2 * (240ns)  = 144ns, anstatt 100ns ohne Adressraum-Virtualisierung bzw. 100ns bei absoluten Adressen.

Der Langzeit-Scheduler verwendet eine dynamische Allokierungs-Strategie (z.B. first fit, best fit) für die zusammenhängende Hauptspeicherzuweisung. Speziell bei Linux wird dazu ein Seiten-Allokierer verwendet, der nach der sogenannten Buddy-Zuweisungs-strategie auf Anfrage physisch aufeinanderfolgende Seitenrahmen bereitstellt. Die Buddy Strategie ist ein Kompromiss zwischen statischer und dynamischer Allokierung; d.h. auch hier kann externe Fragmentierung auftreten. Der Gesamte Speicher wird über eine Partitionierungs-Schablone in „überlappende“ Bereiche jeweils von der Größe einer Zweier-potenz unterteilt; d.h. der größte Bereich entspricht der vorhandenen physischen Speicher-größe. Wenn der Allokierer einen zusammenhängenden Bereich einer bestimmten Länge benötigt, nimmt er das kleinste freie Stück, das mindestens die erforderliche Länge aufweist. Wenn es mehr als doppelt so lang ist wie der benötigte Bereich, so wird es halbiert; das eine halbe Stück wird benutzt, das andere, sein Buddy, bleibt frei. Wann immer ein Stück frei wird und sein Buddy bereits frei ist, werden sie wieder verschmolzen. Dieses Verfahren ist recht einfach zu implementieren, kann aber zu erhöhter interner Fragmentierung führen, denn wenn ein Prozess z.B. 33 Seiten benötigt, belegt er schon 64; d.h. die entstehende interne Fragmentierung ist immer der Rest ungenutzten Speichers bis zur nächsten Zweierpotenz. Der Vorteil dieses Systems ist die die schnelle Zusammenfassung von freien  Speicherblöcken, da nur die entsprechen-den Listen durchsucht werden müssen. Wird z.B. ein 32 KB-Block frei, muß nur die 32 KB-Liste nach freien Blöcken durchsucht werden, damit festgestellt werden kann, ob eine Zusammenfassung möglich ist.

Funktion s.o.; interne Fragmentierung, denn wenn ein Prozess z.B. 33 Seiten benötigt, belegt er schon 64 also fast doppelt so viel wie er eigentlich benötigt; aber auch externe Fragmentierung (externer Verschnitt), weil freiwerdende Blöcke nur mit ihren Buddies rekombiniert werden können; d.h. es kann sein, daß die Hälfte des Hauptspeichers inzwi-schen wieder frei ist, aber trotzdem kein Slot für einen mittelgroßen Block gefunden werden kann.

Ein Prozess soll den Eindruck bekommen, die CPU und den Hauptspeicher allein für sich zu haben. Ferner soll ein Programmierer Programme unabhängig vom physikalischen Adress-bereich und der Größe des Hauptspeichers schreiben können. Daher verwendet ein Programm nur die von den physischen Adressen unabhängigen virtuellen Adressen. Dieses geschieht durch die Abbildung logischer auf physischer Adressen in der MMU z.B. mittels Paging und die Möglichkeit durch Auslagerung scheinbar mehr Programme im „Speicher“ zu halten als eigentlich physisch möglich wäre bzw. nur die gerade benötigten Informationen im Hauptspeicher tatsächlich vorzuhalten (Ein Swap-Bereich auf dem Sekundärspeicher ist für die Speicherung der ausgelagerten Seiten reserviert). Daher ist virtueller Hauptspeicher ein Speicherzuweisungskonzept, bei dem Sekundärspei-cher als Teil des Hauptspeichers mittels Seiten-Auslagerung und Paging adressiert wird.

Basis- und Grenzregister bei der zusammenhängenden Zuweisung, Seitentabelle bei Pa-ging. Untergebracht sind diese Umrechnungs-HW-Einheiten in der MMU und die Tabellen im Hauptspeicher. (Mit Hilfe von Hardware- MMUs lassen sich die Vorteile von Segmentierung und Paging (nur falls in dieser Reihenfolge hintereinandergeschaltet) kombinieren. Die Paging-Einheit bildet frei von externer Fragmentierung (nur) einen großen virtuellen Adressraum (linear adress) auf physische Adressen ab. Die vorangeschaltete Segmentierungs-Einheit teilt den großen virtuellen Adressraum in mehrere unabhängige Adressräume auf, wobei die dadurch auftretende ext. Fragment. nur im virtuellen „linear“-Adressraum auftritt.)

Ein „bereiter“ Prozess wird auch dann „rechnend“ gemacht, falls nicht alle seine Seiten-rahmen im Hauptspeicher stehen. Die fehlenden im Sekundärspeicher stehenden Seiten-inhalte sind anhand des „present-Bits“ im Seiteneintrag der Seitentabelle identifizierbar. Erfolgt ein Zugriff auf eine im Hauptspeicher nicht vorhandene Seite, liegt also ein sog. Seitenfehler (page fault) vor, so löst die MMU eine Software-Unterbrechung (trap) aus, um die fehlenden Daten in den Hauptspeicher zu lesen. Diese Technik wird als „demand paging“ bezeichnet, da Seiten erst bei Bedarf in den Hauptspeicher eingelagert werden. Die Seite im voraus einzulagern, sog. „prepaging“ wäre aufwendiger.

Wenn Daten im Hauptspeicher abgelegt werden sollen und dort kein freier Platz mehr vorhanden ist, müssen alte Daten (des laufenden oder eines anderen Prozesses dynamisch) ausgelagert werden. Die optimale Strategie lagert diejenige Seite aus, die erst am weitesten in der Zukunft wieder benötigt wird, um künftige Seitenfehler möglichst zu vermeiden. Leider steht diese Information in der Regel nicht zur Verfügung. Allerdings ist Least Recently Used (LRU: zeitlich am längsten nicht benutzt) eine Annäherung an diese Strategie. Ein zusätzliches Dirty- bzw. Modified- Bit in jedem Seitentabelleneintrag markiert veränderte/beschriebene Seiten, so daß auch nur veränderte Seiten tatsächlich auf den Sekundärspeicher (z.B. Festplatte) zurückgeschrieben bzw. „verdrängt“ werden müssen.

Die optimale Strategie: Bei der optimalen Strategie (OPT) werden die Seiten zuerst ausgelagert, die entweder gar nicht mehr oder für eine besonders lange Zeitspanne nicht mehr benötigt werden. Die optimale Strategie ist nicht praktikabel.

LRU: Least Recently Used. zeitlich am längsten nicht benutzt worden  (zeitliche Lokalität)

LFU: Least Frequently Used. LFU versucht, den vernünftigen Grundgedanken der LRU-Strategie mit vertretbarem Aufwand zu verfolgen. Es wird die Seite ausgelagert, auf die innerhalb einer gewissen Zeitspanne am wenigsten häufig zugegriffen wurde.

FIFO: First In First Out: leider werden hierbei häufig benötigte Seiten regelmäßig ausgelagert

Die Länge/Breite der logischen Adressen im Adressregister. Die höherwertigen Bits sind ggf. mit den Segmentselektor-Adress-Bits belegt.

Welche Einträge enthält die Seitentabelle? Welche Informationen werden vom BS noch benötigt, um virtuellen Hauptspeicher zu realisieren?

Die Seitentabelle enthält mindestens: Seitenrahmennummer, Present-Bit (für Seiten-fehler), Dirty-Bit (modified), Reference-Bit (wurde referenziert). Bei einem „miss“ bzw. “page fault“ muß das Betriebssystem auch die Adresse der Seite im Sekundärspeicher kennen.

Z.B. gemäß Least Recently Used (LRU).

Werte von Dirty-Bit (Modified-Bit) und Present-Bit.

Ein zusammenhängendes Stück, mehrere zusammenhängende Segmente: First Fit, Best Fit mit Kompaktifizierung, Buddy, (Paging: LRU: Least Recently Used (mit Demand Paging), theoretisch OPT

keine externe Fragmentierung, einfache Verwaltung des Hauptspeichers, Realisierung von

virtuellem Hauptspeicher, gemeinsam genutzte Seiten (shared memory) möglich

Mit Paging ist mindestens ein zusätzlicher Speicherzugriff auf die Seitentabelle erforderlich,

falls kein Adress-Cache (TLB) vorhanden ist.

Größere interne Fragmentierung bei der größeren Seiten, lange Seitentabelle bei der

kleineren Seitengröße.

Unabhängigkeit von Programmen und Rechner; Programme zu schreiben, ohne Wissen von

der Größe des Hauptspeichers; nur die Seiten im Hauptspeicher zu halten, die gerade

gebraucht werden, der Rest bleibt im Sekundärspeicher. Speicher-Zugriffsschutz.

Welche Vorteile und Nachteile hat er?

Für die Realisierung des virtuellen Hauptspeichers muß man die folgenden Probleme lösen:

a). wann eine Seite in den Hauptspeicher geholt werden soll. Demand paging ist eine

Möglichkeit. (Was ist demand paging?)

b). welche Seite ausgelagert (verdrängt) werden soll, wenn der Hauptspeicher voll ist.

Ein Seitenfehler ist eine Unterbrechung aufgrund eines miss/pagefault zwecks Einlagerung

(demand paging) der Seite aus dem Sekundärspeicher, ggf. mit Verdrängung gemäß LRU.

Wie merkt das Betriebssystem, daß eine Seite nicht im Hauptspeicher liegt?

present bit = 0

Zum Sichern von Kontexten bei Unterbrechungen und Unterroutinen/Funktionsaufrufen.

Abstraktion (virtuelle Geräte), Kapselung, Schichtenmodell, Architekturmodell (z.B.

ISA), Schnittstellen, Protokolle, Programmierschnittstelle, Benutzerschnittstelle,

Speicher-Hierarchie, Dateisysteme, „parallele“ Prozesse, Prozesszustände, Pozess-

Synchronisation (Semaphoren), Scheduling-Strategien, Hauptspeicherverwaltung,

virtueller Speicher, Gerätetreiber.

Rollen, Zielgruppen: Benutzer, Anwendungsprogrammierer, Systemadministrator, System-

entwickler.

Threads (Fäden) sind leichtgewichtige Prozesse die sich, im Gegensatz zu

schwergewichtigen Prozessen denselben Adressraum, dasselbe Programm und

dieselben Ressourcen (z.B. Dateien) teilen. Beim Zustandswechsel müssen nur noch

Registerinhalte, wie z.B. der Befehlszähler, Staus-Register (mit S/U-Modus) und Prozess-

Stackpointer “geswappt“ werden, jedoch nicht der Adressraum-Kontext gerettet (und somit

z.B. auch keine virtuellen Adress-Caches „geflusht“) werden, was zeitaufwändiger wäre.

Eine Menge von im selben Adressraum arbeitenden zusammengehörigen Threads, die an

einer Aufgabe arbeiten bzw. dasselbe Programm teilen, bezeichnet man auch als Task.

Dieser kann auch über mehrere Prozessorkerne verteilt sein. Aufgrund des gemeinsamen

Adressraums können thread-individuelle Daten nicht durch die MMU geschützt werden. Die Threads

eines Tasks dürfen sich also nicht gegenseitig stören.v

Registerinhalte, Befehlszähler (Programmzähler), Staus-Register, Prozess-Stapel,

ProzessControlBlock (Threadnummer/ID, Priorität, Zustand) zumindest bei Kernel-

Threads, da diese vom BS-Scheduler genauso wie schwergewichtige Prozesse behandelt

werden. Die Programm und Daten-Adressräume bzw. Segmente sind jedoch nicht

thread-spezifisch, werden also zwischen allen Threads eines Tasks „geshared“. Das

hat den Vorteil, daß die Threads eines Tasks auf gemeinsamen geteilten Daten arbeiten

können. Solche Zugriffe auf gemeinsame Daten müssen jedoch synchronisiert werden.

Gegenseitiger Zugriff auf thread-eigene Daten kann nur durch „kooperatives“ Verhalten vermieden

werden, da kein Speicherschutz zwischen den Threads vorhanden ist.

Jeder Prozess hat einen eigenen (geschützten) Adressraum und einen Ausführungspfad,

der durch den Befehlszähler beschrieben wird. Wenn ein Prozess mehrere Ausführungs-

pfade hat, dann ist jeder Ausführungspfad ein Thread.

Mehrere Threads teilen sich ein Programm, den Adressraum bzw. die Adressräume

(Codesegment, Datensegment) und dieselben Dateien; jedoch besitzt jeder Thread sei-

nen eigenen Registersatz (insbesondere einen eigenen Befehlszähler/Programmzähler,

Statusregister und Stack-Pointer) und einen eigenen Stack-Bereich. Die Threads eines

Tasks haben also einen gemeinsamen Adressraum, ein gemeinsames Programm aber

unterschiedliche Ausführungspfade. Threads können über das gemeinsame RAM-

Datensegment unkompliziert kommunizieren. Der Aufwand beim Thread-Wechsel ist

wesentlich geringer als beim Prozesswechsel.

Threads: Wenn eine Aufgabe für verschiedene Clients effizient, also quasiparallel

angeboten werden soll (z.B. ein Thread pro Client auf einem Datei/Web-Server). Während

einige Threads z.B. auf E/A warten (blockieren), kann ein anderer Thread

weiterarbeiten. Wenn blockierende Aufrufe auftreten (z.B. E/A-Systemaufrufe), müssen

Kernel-Treads verwendet werden, da nur diese (im Gegensatz zu Benutzer-Threads) von

Betriebssystem „gescheduled“ werden, und somit die Effizienz von Quasiparallelität erreicht

werden kann. Des weiteren bieten sich Threads an, falls quasiparallel auf denselben

gemeinsamen Daten im Hauptspeicher gearbeitet werden soll bzw. über das gemeinsame

Datensegment kommuniziert werden soll (was jedoch auch schwergewichtige Prozesse

mit gemeinsamen „shared memory“-Bereichen können, jedoch mit insgesamt erhöhtem

Kontextwechsel-Aufwand).

Schwergewichtige Prozesse: Bei individuellen Aufgaben mit zu schützenden lokalen, also

nicht „gesharedten“ Daten.

Der Aufruf von fork (ohne Parameter) bewirkt, daß eine genaue Prozess-Kopie vom

schwergewichtigen Elternprozess erzeugt und bereit gemacht wird; auch die Registerinhalte,

insbesondere der Inhalt des Befehlszählers, werden in den neuen Kontext (Adressraum-

Speicherbereiche, Register, Befehlszähler, Stackinhalt, PCB und teils Ressourcenliste)

kopiert (wann genau das erfolgt (copy-on-write, lazy copying) und in welchem genauen Umfang, z.B. für das

Read-Only-Code-Segment, wird jedoch im Kurstext nicht genau erwähnt).

Nicht ohne Nachteile: Entweder nimmt man ein Blockieren aller Aufträge bzw. des

gesamten Tasks beim Aufruf einer E/A-Funktion in kauf oder man verwendet nicht

blockierende Aufträge bzw. Aufrufe, was einer Art Polling entspricht, und verwaltet die

Auftragsstati explizit anstatt implizit über die einzelnen Thread-Befehlszähler (Stichwort:

Blockieren oder Verschachteln). Auch bei der Verwendung von blockierenden

Sytemaufrufen innerhalb von Benutzer-Threads tritt dasselbe Problem auf; d.h. der

gesamte Task, also z.B. der gesamte Datei-Server, wird bei den E/A-Aufrufen blockiert.

Die Verwendung mehrere schwergewichtiger Prozesse führt wiederum zu erhöhtem

Adressraum-Kontext-Wechsel-Aufwand beim Prozesswechsel und das obwohl ein

gemeinsamer Hauptspeicherbereich ausreichen würde und für einen Datei-Server sogar von

Vorteil wäre. Die Verwendung von mehreren Threads für den Datei-Server ist daher

eleganter: während einer von ihnen blockiert, weil er z.B. auf die Erledigung eines Ein-

/Ausgabebefehls wartet, kann ein anderer Thread rechnen.

Leichtgewichtige Prozesse können als Kernel-Threads oder als Benutzer-Threads

implementiert werden. Kernel-Threads werden über die System-Funktion clone (vererbt im

Gegensatz zu fork auch den Speicherbereich des Erzeugerprozesses; d.h. die Speicherbereiche

werden geshared) generiert und werden vom Betriebsystem genauso wie schwer-

gewichtige Prozesse (im eigenen PCB) verwaltet bzw. „gescheduled“. Bei Benutzer-

Threads geschieht das Scheduling der einzelnen Threads hauptsächlich im Anwender-

kontext, d.h. mittels Bibliotheksaufrufen. Das Scheduling der Task-Threads ist somit

schnell und läßt sich von Anwerberebene steuern. Das Betriebsystem „weiß“ jedoch nichts

von diesen Benutzer-Threads, sondern sieht nur den gesamten Task als schwergewichtigen

Prozess.

Beim „clonen“ eines leichtgewichtigen System-Prozesses (Kernel-Thread) wird neben

dem Programm-Code zusätzlich das (identische Codesegment,) Datensegment und

verwendete Ressourcen vererbt (Der Programmzähler wird im Gegensatz zu fork nicht geklont,

man kann aber den als Parameter übergebenen Funktions-Pointer auf das selbe Programmsegment

zeigen lassen und erreicht so die direkte „Programmvererbung“).

Die einzelnen Thread-Kontexte auf dem Stapel würden durchmischt und es käme zum

Prozess-Absturz, z.B. weil noch auf dem Stapel befindliche Funktions-Parameter des

vormals rechnenden Threads nun z.B. als Rücksprungadressen interpretiert werden

könnten.

Um Rechenprozesse zu beschleunigen können Berechnungen auf mehrere gleichzeitig

laufende Prozesse oder Threads mit Zugriff auf gemeinsam geteilte Daten(segmente)

wie z.B. gemeinsam verwendete Variablen aufgeteilt werden.

Da z.B. atomar auszuführende „Read-Modify-Write“-Zugriffe i.a. nicht unteilbar imple-

mentiert sind sondern in realen Programmen aus mehreren Instruktionen bestehen,

können nichtdeterministische quasi-zeitgleiche Zugriffen auf gemeinsame Variablen zur

inkonsistenten Ausführung dieser Operationen führen, was ggf. die Verfälschung der

Variablenwerte zufolge hat. Dieses kann z.B. durch einen Prozesswechsel inmitten der

Zugriffs-Operation oder bei Multicore-System durch sehr zeitnahe abwechselnde bzw.

verzahnte Speicher-Zugriffe auf die Variable geschehen. Je nach zeitlicher Prozess-

Zugriffsreihenfolge hat die Variable am Ende ein anderes ggf. verfälschtes Ergebn

Dieses ist jeweils ein Abschnitt im Programm in dem auf zwischen parallel laufenden

Prozessen geteilte Ressourcen, wie z.B. eine gemeinsame Variable, zugegriffen wird,

so daß dort eine „race condition“ entstehen kann, wodurch der Inhalt der

gemeinsamen Variable verfälscht wird. Eine „race condition“ kann entstehen, falls

parallellaufende Prozesse gleichzeitig auf z.B. eine gemeinsame Variable sog.

unteilbare Operationen nicht atomar ausführen und durch den gleichzeitig stattfindenden

Zugriff die Atomaritäts-Bedingung der Operation(en) verletzen. Im allgemeinen wird von

mehreren kritischen Abschnitten in einem Programm aus auf ein und dieselbe

gemeinsame Variable zugegriffen. Um „race conditions“ zu vermeiden, bzw. um die

Atomarität der Operationen auf gemeinsame Variablen zu gewährleisten, darf gleichzeitig

immer nur ein kritischer Abschnitt bezüglich einer Variable durchlaufen werden. Diese

Einschränkung nennt man „exklusiven Zugriff“ und sie wird durch „Synchronisation“

erreicht. Race conditions lassen sich vermeiden, indem nie mehr als ein Prozess in

einen kritischen Abschnitt eintritt. Dieses läßt sich mithilfe von Synchronisation erreichev

Der Scheduler muß immer dann tätig werden, wenn durch eine Unterbrechung ein

Prozesswechsel erzwungen wird; die Unterbrechung kann zu beliebigen Zeitpunkten

stattfinden. Er hat keine Informationen über das Verhalten der Prozesse in der

Zukunft. Es ist ihm auch nicht möglich, solche Informationen durch statische oder

dynamische Analyse der Programme zu gewinnen. Es ist sowieso nicht garantiert, daß es

überhaupt einen auf Zeitscheibenlängen basierenden korrekten Ablaufplan gibt. Der

Scheduler kann die Synchronisation von Prozessen bzw. Threads also nicht

übernehmen; daher sind sie selbst für die Synchronisation verantwortlich.

Parallele Prozesse verwenden gemeinsame Daten, dabei greifen sie in unvorhersehbarer

Reihenfolge quasi-gleichzeitig z.B. auf eine gemeinsame Variable zu. Enthält z.B. eine

Operation auf diese gemeinsame Variable eine atomar auszuführende Befehls-

Sequenz aus mehreren Instruktionen (z.B. einen „Read-Modify-Write“-Zugriff), so kann durch einen unvorhersehbaren parallelen Variablen-Fremdzugriff inmitten der atomaren

Instruktions-Sequenz die unterbrochene Operation inkonsistent ausgeführt werden,

wodurch der Variablenwert ggf. verfälscht wird. Man kann diese sog. „race conditions“

vermeiden, indem gleichzeitig immer nur eine atomar auszuführende Sequenz einer

Operation auf ein und dieselbe Variable durchlaufen wird, also immer nur einem Thread

bzw. immer nur einem kritischen Abschnitt „exklusiven Zugriff“ auf die gemeinsame

Ressource gestattet wird. Diese „Serialisierung“ der „kritischen Abschnitte“ bzgl. z.B. einer

gemeinsamen Variablen nennt man Synchronisation. Sie verhindert gleichzeitige Zugriffe

und somit die Unterbrechung atomar auszuführender Operationen und der dabei

entstehenden Inkonsistenzen innerhalb gemeinsamer Variablen. Somit hängt das

Ergebnis der Variablen-Operationen nicht mehr von der unvorhersehbaren Ausführungs-

reihenfolge der Prozess-Zugriffe ab, da diese verhindert werden.

Kurzform: Die Synchronisierung soll race conditions verhindern, indem konkurrierenden

Threads/Prozessen ein exklusiver Zugriff garantiert wird, solange sie sich in einem kritischen

Abschnitt befinden; d.h. das Betreten und Verlassen eines kritischen Abschnitts muß

zwischen Prozessen abgestimmt werden, z.B. durch zwei den Abschnitt umschließende

Betriebssystem-Funktionen „enter_critical_section()“ und „leave_critical_section()“.

Man kann zumindest bei „Single-Core“-Systemen durch Blockieren des Zeitscheiben-Timer-Interrupts einen Aufruf des Schedulers und damit einen Prozesswechsel und potentiellen Parallelzugriff auf eine zwischen den Prozessen gemeinsam genutzte Variable verhindern; d.h. der Scheduler-Aufruf würde verhindert während irgendein kritischer Ab-schnitt durchlaufen wird. Die Interrupt-Sperrung erfordert jedoch (nicht ohne Grund) Systemrechte und die temporäre Sperrung verhindert für die Dauer eines atomar auszuführenden Abschnitts das gesamte Scheduling (Diese Lösung ist also nicht gerade „variablen- bzw. operations-granular“). Außerdem geschieht dieses auf Kosten des Echtzeitverhaltens des Gesamtsystems, da auch hochpriore Prozesse nun ggf. verzögert „rechnend“ werden. Es entsteht dadurch sogenannter Jitter bzw. sogenanntes zeitliches Jittern. Eine bessere Lösung ist es auf spezielle atomare Maschinencode-Zugriffs-instruktionen (ggf. mit Bussperrung) zurückzugreifen.

Die herbeigeführte „Serialisierung“ bzw. Koordinierung des Durchlaufens „kritischen Abschnitte“ bzw. atomar auszuführender Operationen auf gemeinsamen Daten wie z.B. einer gemeinsamen Variable zwecks Verhinderung von race conditions (atomaritäts- und konsistenzsverletzende Parallelzugriffe) nennt man Synchronisation.

Der kritische Abschnitt im Thread Beobachter liegt inmitten der Zeile „Zähler:=Zähler+1“, da der Berichter-statter vor dem Zurückschreiben des inkremetierten Wertes Zähler aus-geben und sein „Zähler:=0“ ausführen könnte. Der dann richtige Wert 0 würde später durch den inkrementierten Wert überschrieben werden. Der kritische Abschnitt im Thread Bericherstatter umfasst die beiden Zeilen „print(Zähler)“ und „Zähler:=0“, da der Beobachter zwischen den beiden Operationen Zähler (ggf. öfters) inkrementieren könnte. Diese Inkremente gingen dann allerdings aufgrund des danach ausgeführten „Zähler:=0“ verloren. Die Einführung einer Synchronisationsvariable bewirkt zwar „exklusiven Zugriff“ und somit Synchronisation, erlaubt aber nur eine echte abwechselnde Vergabe (birgt Starvation Gefahr) des exklusiven Zugriffs und hat zudem ein „geschäftiges Warten“ (busy waiting) im rechnenden Zustand des jeweils wartenden Threads zur Folge. Wenn die Variable switch mit 1 initialisiert wird und der Prozess Beobachter eine höhere Priorität beim Scheduling als der Prozess Berichterstatter hat, dann kann der Berichterstatter aufgrund seiner geringeren Priorität Switch nie auf 0 setzten und der höherpriore Beobachter wartet ewig aktiv (via busy waiting) in der Zeile „while switch = 1 do no-op“. Zwischen den beiden Prozessen/Threads existiert dann also ein Deadlock.

Race conditions lassen sich vermeiden, indem nie mehr als ein Prozess in einen kritischen Abschnitt eintritt (exklusiver Zugriff). Dieses läßt sich mithilfe von Semaphoren sicherstellen.

Ein Semaphor S ist eine vom Betriebsystem unterstützte Synchronisationsvariable mit einer Warteschlange, welche nicht die Nachteile der „applikativen einfachen“ Synchroni-sationsvariable aufweist. Ein Semaphor ist ein vom Betriebsystem unterstütztes Signali-sierungskonzept zur Prozessynchronisation ähnlich einer Vehrkehrsampel. Er ist ein abstrakter Datentyp mit einer globalen Zähl-Variablen, einer Prozess-Warteschlange und den Funktionen bzw. Operationen init, down und up.

Das Konzept des Semaphors (Zeichenträger) wurde von Dijkstra zur Lösung von Problemen entwickelt, bei denen mehrere Prozesse oder Threads ein Betriebsmittel belegen wollen, von dem insgesamt n Stück zur Verfügung stehen. Dabei kann es sich um n freie Speicherplätze handeln, um n CPUs oder um das Recht, in den kritischen Abschnitt eintreten zu dürfen. Im letzten Fall ist n = 1, weil ja zu einem Zeitpunkt immer nur ein Prozess seinen kritischen Abschnitt betreten darf. Ein Semaphor S kann als abstrakter Datentyp spezifiziert werden. Der Zustand von S besteht aus der Anzahl freier Betriebsmittel, gespeichert in einer Zählvariablen count, und einer Prozessmenge W. Falls count ≠ 0, so ist W leer, ansonsten enthält W alle Prozesse, die sich bisher vergeblich um ein Betriebsmittel bemüht haben und darauf warten, daß wieder eines frei wird. Auf S sind zwei Operationen definiert, down und up. Wenn ein Prozess ein Betriebsmittel benutzen will, ruft er die Operation down(S) auf. Wenn ein Prozess sein Betriebsmittel wieder freigibt, ruft er die Operation up(S) auf (Die Variable S.count darf nach der Initialisierung nur über die down- und up-Anweisungen benutzt, aber nie direkt abgefragt oder gar geändert werden):

Semaphore verlagern das Problem der Synchronisation des Durchlaufens kritischer Abschnitte von der Anwenderebene auf das Betriebssystem. Die Semaphor-Operationen down und up zur „Realisierung kritischer Abschnitte“ enthalten jeweils wiederum einen kritischen Abschnitt bestehend aus den beiden Zeilen „if S.count > 0“ und „then S.count:= S.count – 1“ in down(S) welche beide eine einzige atomare auszu-führenden Operation darstellen und auch die Zeilen: „if S.W ist nicht leer“ mit “S.count := S.count +1“ in up(S). Letzterer Schadensfall: S.W werde als leer detektiert; bevor S.count inkrementiert wird, durchläuft ein anderer Prozess down(S), blockiert und wird nicht aufgeweckt, obwohl S.count inzwischen inkrementiert wurde. Diese beiden Abschnitte sind allerdings laufzeittechnisch (z.B. durch atomare Assembler-Instruktionen) optimiert und führen zu keinem oder wenig Jitter: Kritische Abschnitte eines Anwenderprogramms, welche durch eine Semaphore synchronisiert/realisiert werden, dauern i.a. wesentlich länger als das kurze Durchlaufen der kritischen Abschnitte der Operationen down und up. Die effektiven Scheduling-Blockaden sind somit, falls überhaupt vorhanden, wesentlich kürzer.

Er wird von einem gerade im kritischen Abschnitt befindlichen Prozess beim Verlassen des selbigen via up() aufgeweckt. Er wird in den Zustand „bereit“ versetzt und die Zählvariable bleibt für ihn um eins „reservierend“ erniedrigt. Dieses muß so erfolgen, da er gemäß der down-Implementierung nach dem „rechnend werdend“ die down-Operation nicht nochmal durchläuft, sondern direkt in den kritischen Bereich eintritt (wäre dies anders gelöst, könnte er oder ein anderer wartender Prozess mangels Fairness verhun-gern).

Synchronisationsvariablen: busy waiting, nur zwei Konkurrenten immer abwechselnd. Semaphore: blockierend (effizient), wahlfreie Zugriffe mehrerer (auch mehr als zwei) Konkurrenten erlaubt.

Die Vermeidung von busy waiting, da wartende Prozesse blockiert werden. Keinen erzwungenen abwechselnden Zugriff wie etwa bei der Verwendung einer Synchro-nisationsvariablen. Die mittels der Funktionen down und up ins Betriebssytem ausgelagerten kritischen Abschnitte sind viel kürzer als auf applikativer Ebene und können z.B. mittels spezieller Assembler-Instruktionen oder via Interrupts atomar implementiert werden. 

Durch Verwendung von einer Zeitgeber-Interrupt-Sperre in Single-Core CPUs oder besser durch atomare „read-modify-write“ Maschinenbefehle wird der Prozesswechsel während des Durchlaufens der kritischen Abschnitte der Semaphor-Operationen down und up unter-bunden.

Die Zeilen: „if S.W ist nicht leer“ mit “S.count := S.count +1“ in up(S) müssen zusammen atomar (unteilbar) ausgeführt werden, aber auch schon die Anweisung “S.count := S.count +1“ alleine muß, obwohl sie ganz am Ende steht, für n > 1 atomar ausgeführt werden.

Die Zählvariable des Semaphor S.count wird mit Eins initialisiert und beide kritischen Abschnitte werden durch S synchronisiert. Der Semaphor S wird hier also „binär“ genutzt.

Ein Semaphor der nur die Werte Null bis Eins annehmen kann. Man spricht hier von mutual exclusion (gegenseitiger/wechselseitiger Ausschluß).

(Eine Spezialisierung und gleichzeitig auch Erweiterung „binärer Semaphoren“ sind die Mutexe: Mutexe sind Schlösser die im Gegensatz zu Semaphoren vom ersten in den kritischen Abschnitt eintretenden Prozess „gelockt“ und auch via PCB „besessen“ werden bis der kritische Abschnitt wieder verlassen wird. Dabei darf der temporär besitzende Prozess den kritischen Bereich wiederholt betreten während alle andere Prozesse dabei blockiert werden, bis er ihn gleichhäufig wieder verlassen hat. Gezählt wird hierbei also die Anzahl der Eintritte des besitzenden Prozesses.)

Die erste Idee wäre es nur einen Semaphor „Frei“ zu verwenden, Frei.count mit n, also der Anzahl Betriebsmittel zu initialisieren und down(Frei) und up(Frei) wie im Listing bereits gezeigt zu platzieren. Jedoch könnte dann der Verbraucher via up(Frei) den Wert von Frei.count auf einen beliebigen Wert größer als n inkrementieren. Die Lösung bietet hier ein zweiter Semaphor „Belegt“ der in Gegenrichtung zählt und daher mit Null initialisiert wird. Um den Puffer-Zugriff an sich zu synchronisieren wird noch ein binärer Semaphor „Zugriff“ benötigt. Verändert man die Verschachtelungsreihenfolge von Zugriff down und up jeweils nach außen führt diese in beiden Fällen zum Verhaken (zum Deadlock). Im Erzeuger kann es dann passieren, daß der Erzeuger bei vollem Puffer blockieren muß und den Verbraucher gleichzeitig daran hindert ein Objekt dem vollen Puffer zu entnehmen. Im Verbraucher kann es passiere, daß der Verbraucher bei leerem Puffer blockiert und den Erzeuger gleichzeitig daran hindert ein Objekt dem leeren Puffer hinzuzufügen.

Zwei oder mehrere Prozesse blockieren sich gegenseitig z.B. über zwei (hier ungünstig vertauschte) hintereinander liegende also sozusagen „ver-und-ete“ Semaphoren:

Prozess Erzeuger: down(Zugriff); down(Frei); up(Zugriff);                     mit init Zugriff = 1

Prozess Verbraucher: down(Zugriff); up(Frei); up(Zugriff).                und Frei sei aktuell = 0 Der Erzeuger blockiert in down(Frei) und wartet auf up(Frei), dieses wird aber nie geschehen, weil der Verbraucher in down(Zugriff) blockiert daher up(Frei) nie ausführen kann. Das liegt daran, daß die Freigabe einer Ressource (Frei) erst den Erhalt einer anderen Ressource (Zugriff) bedingt.

Paging und Segmentierung bieten beide Speicher-Zugriffsschutz und „Relokierbarkeit“ und unterstützen so die dynamische Allokierung. Die interne Fragmentierung ist bei beiden Virtualisierungs-Methoden vorhanden, hat aber keine nennenswerte Auswirkung.

Paging: hat nicht das Problem der externen Fragmentierung und es ist auch keine gelegent-liche Kompaktifizierung des Hauptspeichers bei der Einlagerung/Laden eines Prozesses nö-tig. Paging bietet nur einen Adressraum pro Prozess, was bei wachsenden logischen Daten-blöcken zu Kollisionen im logischen Adressraum führen kann. Es unterstützt implizit  gemein-same „gesharedte“ („öffentliche“) Speicherbereiche zwischen verschiedenen Prozessen.

Segmentierung: führt zu externer Fragmentierung, bietet aber mehrere Adressräume pro Prozess. (Falls hardwaremäßig mehr Segmente als nur RAM-Daten-, Stack-, Programm- und konst.-Daten-Segment unterstützt werden, können, wie auch beim Paging, Bereiche zwischen Prozessen „geshared“ werden, um z.B. Interprozesskommunikation oder auch theoretisch gemeinsam genutzte Code-Segmente zu ermöglichen.)

Ausführung der down-Operation durch einen Prozess bedeutet, zu fragen, ob er etwas machen darf.

Ausführung der up-Operation durch einen Prozess bedeutet, anderen Prozessen bescheid zu sagen, daß die Ressource wieder freigegeben ist.

Verwendung:

1. Schützen eines kritischen Abschnitts durch Semaphor S: down(S), kritis. Abschnitt, up(S).

2. Signalisieren um z.B. die abwechselnde Reihenfolge von Operationen zu garantieren:

 Beispiel: Prozess A: down(S1), kritischer Abschnitt von A, up(S2).

Prozess B: down(S2), kritischer Abschnitt von B, up(S1).

Eine Anzahl von n Philosophen die jeweils denken, hungrig sind oder essen sitzen an einem Tisch und teilen sich n Eßstäbchen, wovon jeder Philosoph immer zwei Stäbchen zum essen benötigt. Eine erste Idee zur Implementierung einer funktionierenden Lösung dieses Aufgabe wäre wie folgt:

Bei dieser Lösung gibt es aber einen Nachteil: Ein Deadlock aller Philosophen-Prozesse tritt auf, wenn jeder Philosoph via down(Slinks(i)) zeitnah zu den anderen Prozessen sein linkes Stäbchen aufnimmt: dann kann keiner ein rechtes erhalten, das ja sein rechter Nachbar hat, der ebenfalls auf sein rechtes Stäbchen wartet. Alle Prozesse blockieren hierbei also in down(Srechts(i)). Man löst das Problem dieser Blockade, indem ein Philosoph nur dann Stäbchen aufnehmen darf, wenn beide frei sind. Dazu braucht man einen binären Semaphor „mutex“, der mit 1 initialisiert wird. Bevor ein Philosoph versucht, die Stäbchen zu nehmen oder zurückzulegen, führt er eine down-Operation auf mutex aus. Nachdem er die Stäbchen genommen oder zurückgelegt hat, führt er eine up-Operation auf „mutex“ aus. Es kann also immer nur ein Philosoph gleichzeitig Stäbchen nehmen oder zurücklegen. Kann aber ein Philosoph nicht beide Stäbchen aufnehmen, so wird er schlafen gelegt. Das wird realisiert, indem jeder Philosoph i einen Semaphor p[i] hat, der mit 0 initialisiert wird. Das Ziel des Semaphors p[i] ist, den i-ten hungrigen Philosoph zu blockieren, d. h. warten zu lassen, falls eins seiner beiden Stäbchen nicht frei ist. Jeder Philosoph i benötigt noch eine Statusvariable status[i], um zu verfolgen, ob er gerade hungrig ist oder denkt oder ißt. Ein Philosoph kann nur in den Zustand von Essen übergehen, wenn seine beiden Nachbarn nicht beim Essen sind. Dieser status[i] wird zu Anfang auf Denken gesetzt. Die Prozedur teste(i) stellt fest, ob der Philosoph i hungrig ist und die zwei Stäbchen bekommen kann. Wenn ja, dann geht er in den Zustand „Essen“ über. Man beachten, daß die Prozedur teste sowohl von Philosophen für sich selbst aufgerufen wird (in stäbchen_nehmen) als auch für seine Nachbarn (in stäbchen_weglegen). Außerdem wird es hier nicht automatisch „gerecht“ zugehen, was die Verteilung der Essenszeiten angeht.

Ein Dateisystem bietet den Benutzern eine logische Sicht auf Dateien an; d.h. physische Eigenschaften wie z.B. Operationen auf Daten-Blöcke werden verborgen. Z.B. soll ein Benutzer Operationen von der Benutzerschnittstelle wie z.B. Erzeugen, Öffnen, Lesen, Schreiben, Entfernen, Ändern von Dateien ausführen können. Der Benutzer braucht sich dabei nicht mit der physischen Struktur des Sekundärspeichers (Festplatte) auseinander-zusetzen (sog. Transparenz bzw. „Durchsichtigkeit“ der untergeordneten Schichten). Das Dateisystem ist für die Abbildung der Dateien auf Blöcke des Sekundärspeichers zuständig.

Blockoperationen

Eine Datei stellt aus logischer Sicht ein Array von Bytes (im Kontext von Datenbanken: eine Folge von Datensätzen) dar, die zusammengehörige Informationen enthalten und die an jeder Position mit einer Index-Nummer gelesen und geschrieben werden können. Aus physischer Sicht ist eine Datei eine Folge gleich großer Blöcke. Jede Datei hat einen Namen. Dessen Datei-Typ-Erweiterung wird auch als Suffix bezeichnet. Dateien lassen sich anlegen, löschen, öffnen, schließen, lesen, beschreiben und ändern.  cp (copy), mv

Verzeichnisse fassen Dateien zusammen. Ein Verzeichnis (directory) ist unter Unix selbst wieder eine Datei. Es enthält eine Menge von Dateinamen und deren Speicherorte im Dateisystem. In einem hierarchischen Dateisystem bzw. in einem Verzeichnisbaum gibt es ein Wurzelverzeichnis (root directory) /. Jedes Verzeichnis zeigt wieder auf andere Verzeichnisse und Dateien (unter Unix ist das aktuelle Verzeichnis (directory) mit pwd erfragbar). Ein Dateiname ist ein Pfad wie z.B. /home/mueller/projekt von der Wurzel bis zu einem Blatt oder einem inneren Knoten. Für jede Datei in einem Verzeichnis gibt es einen Hardlink (Dateinamen mit inode-Referenz) als Eintrag. Ein Verzeichnis hat mindestens zwei Hardlinks, da ein Verzeichnis in seinem Eltern-Verzeichnis (..) und in seinem eigenen Verzeichnis (.) eingetragen wird. der command-shell Befehle cd (change directory), mkdir, rmdir, rm -r(Sicherheitsproblem!), touch.

FAT: im Verzeichnis stehen die Dateinamen und deren Startblocknummern.

inode: im Verzeichnis stehen die Dateinamen und deren inode-Nummern.

Ein Hardlink ist ein Verzeichniseintrag (eine Art von Tupel aus Dateiname und der Datei-inode-Nummer). Jede Datei hat genau einen inode (dieser enthält die Datei-Attribute und die Datei-Blockstruktur) und mindestens einen Hardlink der auf den iniode verweist. Eine Datei kann auch mehrere Namenseinträge (hardlinks) in den Verzeichnissen (nur innerhalb ein und des selben Dateisystems) haben, welche dann alle den selben Datei-inode referenzieren. Um Rekursionen zu vermeiden sind hardlinks auf Verzeichnisse nicht zulässig.

Bzgl. Anzahl der Links: Die Anzahl der Hardlinks einer Datei (Blatt im Dateibaum) ist die Anzahl ihrer eingetragenen Namen in den Verzeichnissen. Die Anzahl der Hardlinks eines Verzeichnisses ist die Anzahl der eingetragenen Dateinamen in seinem Verzeichnis plus 2. Eine Datei kann erst gelöscht werden, wenn die Anzahl der Hardlinks im inode den Wert 0 erreicht.

Für jede Datei werden für jede Benutzerklasse (user, group, others) die Zugriffsarten (r,w,x) individuell festgelegt. Rechte an einem Objekt vererben sich übrigens nicht automatisch auf kleinere Benutzerklassen.

siehe Benutzerklassen-Zugriffsrechte und Zugriffsart: user, group, others , r w x

Der Datei-Eigentümer oder der Superuser.                     Bsp: „chmod g+w myprogram“

Ein Softlink ist eine spezielle Datei, der Inhalt der Datei ist ein absoluter oder relativer Pfad zu einer Datei, ähnlich wie die Windows-Datei-Links.

Ein inode-System ist ein dezentrales Dateisystem. Jede Datei hat genau einen inode. Dieser enthält die Datei-Attribute und die Datei-Blockstruktur, aber keinen Dateinamen. Das finden von Dateiblöcken der Datei geschieht mit einem inode in logarithmischer Zeit. Ein inode wird erst in den Hauptspeicher geladen wenn er gebraucht wird.

Die Datei-Attribute, 13 Block-Adressen und 3 n-fach-Indexblock-Referenzen.

Ein inode braucht wenig Speicherplatz, z.B. 128 Byte in Ext-2. In einem Block auf einer Festplatte können mehrere inodes gespeichert werden. Ein Bereich in der Partition wird für inodes reserviert. Die Anzahl der inodes wird bei der Formatierung der Partition festgelegt und kann nicht mehr geändert werden, was dazu führen kann, daß die Platte bereits „voll“ sein kann, obwohl physikalisch noch viel Platz auf der Platte frei ist. Das inode System bietet auch keine unmittelbare Übersicht über noch freie Blöcke.

Ein inode-System ist ein dezentrales Dateisystem.

Es gibt viele kleine Dateien und der Zugriff auf kleine Dateien muß besonders schnell sein. Die Suche nach einem Block in einer großen Datei soll trotzdem effizient sein.

Die Datenstruktur inode:

Ein inode bei Ext-2 enthält insgesamt 15 Adressen.

Die ersten 12 Adressen zeigen jeweils auf einen Datenblock.

Die 13. Adresse zeigt auf einen Indexblock, in dem x Adressen liegen. Jede der Adressen zeigt auf einen Datenblock.

Ein Indexblock ist genauso groß wie ein Datenblock (und viel größer als ein inode) und wird gemischt mit den Datenblöcken gespeichert.

Die 14. Adresse zeigt auf einen Indexblock, in dem x Adressen liegen. Jede der Adressen zeigt wieder auf einen Indexblock mit x Adressen, die jeweils auf einen Datenblock zeigen. Die 15. Adresse referenziert  dann entsprechend dreifach-indirekt-indizierte Datenblöcke.

Drei bei dreifacher indirekter „Indizierung“ (ohne den Block dabei zu lesen)

12 + x + x^2 + x^3 Blöcke bei Nutzung der „mehrfach indirekten Indizierung“

Die zentrale File Allocation Table (FAT) ist ein Array/Tabelle von verketteten Blockadressen; d.h. der FAT Tabellen-Index selbst identifiziert die physische Blocknummer. Jeder FAT-Eintrag enthält einen Tabellenidex welcher den Folgeblock in der Datei repräsentiert oder er enthält eine der Werte „eof“ oder „free“. Für jeden Block auf der Festplatte gibt es also einen Eintrag in der FAT.

In den Verzeichnissen stehen jeweils Listen von Dateinamen und die Nummern der Startblöcke der Dateien.

Kurzform:

1. Es gibt für jeden Block auf der Festplatte einen Eintrag.

2. Ein Index der FAT ist eine Blocknummer der Festplatte.

3. Ein Eintrag in der FAT ist die Blocknummer (ein Index der FAT) des Folgeblocks der     Datei.

4. Die Größe der FAT = Anzahl der Blöcke x Länge einer Blocknummer.

Die Anzahl der Blöcke auf der Festplatte mal die Länge/Breite einer Blockadresse.

Bsp. Partitions-Größe: 32 GByte, Blockgröße: 4 KByte, 8 Mio. Einträge, ein Eintrag ist 23 Bit breit: 2^23 * 23bit = 23MB.

Durch sequenzielle Suche in der FAT (Die FAT bleibt im Hauptspeicher permanent, solange das System läuft).

Das Auffinden von Blöcken am Dateiende dauert länger (lineare Suchzeit). Dafür bietet FAT

eine schnelle globale Übersicht über z.B. freie Blöcke innerhalb der Partition.

weitere Stichworte im Zusammenhang mit der internen Struktur von Dateisystemen: Block, zusammenhängende Speicherung (hat die gleichen Probleme wie die zusammenhängende Segment-Speicherzuweisung), externe Fragmentierung, nicht zusammenhängende Speicherung, verkettete Liste, kein wahlfreier Zugriff

In der zweiten Kurseinheit werden Prozesse und Dateisysteme als wichtige Teilbereiche von Betriebssystemen näher betrachtet. Als Beispiel zu beiden Bereichen werden die Erzeugung eines Prozesses, die Organisation von Dateien und das Dateisystem unter UNIX/Linux vorgestellt.

Starten beim Datei-inode und dann ggf. Berechnung der Lage des Indexblocks und Laden des Indexblocks (ggf. dreimal hintereinander) in insgesamt logarithmischer Zeit bzgl. Datei-größe (logarithmische Block-Suchzeit).