View
21
Download
0
Category
Preview:
DESCRIPTION
Basisinformationstechnologie HK-Medien. Teil 1, 7.Sitzung WS 02/03. Pipelining. Eine Pipeline ist eine Warteschlange, in der sich die als nächstes abzuarbeitenden Befehle befinden. Jeder Befehl besteht aus Phasen (5-25), z.B.: S1: Befehlsbereitstellung S2: Dekodieren des Befehls - PowerPoint PPT Presentation
Citation preview
BIT – Schaßan – WS 02/03
Basisinformationstechnologie
HK-Medien
Teil 1, 7.SitzungWS 02/03
BIT – Schaßan – WS 02/03
Pipelining
Eine Pipeline ist eine Warteschlange, in der sich die als nächstes abzuarbeitenden Befehle befinden.Jeder Befehl besteht aus Phasen (5-25), z.B.:
S1: BefehlsbereitstellungS2: Dekodieren des BefehlsS3: Lesen der beteiligten RegisterS4: ALU-OperationS5: Schreiben in das Ziel-Register
BIT – Schaßan – WS 02/03
Pipeline Beispiel
aktueller Inhalt der Pipeline
Befehl 1 S1 S2 S3 S4 S5Befehl 2 S1 S2 S3 S4 S5Befehl 3 S1 S2 S3 S4 S5Befehl 4 S1 S2 S3 S4 S5Befehl 5 S1 S2 S3 S4 S5
Die verwendeten Befehle dürfen aber keine Zwischenbeziehungen haben!
BIT – Schaßan – WS 02/03
Aufbau von Assemblerprogrammen
Assemblerprogramme sind aus mehreren Segmenten aufgebaut:
Code-SegmentDaten-SegmentStack-Segment
Vom Programm werden Inhalte der Segmente und deren relative Lage festgelegt
BIT – Schaßan – WS 02/03
Lage der Segmente
Die Segmente können sich in demselben Bereich überlagern
.model tiny: alle Segmente liegen im selben Bereich.model small: jedes Segment hat einen eigenen Bereich
BIT – Schaßan – WS 02/03
Programmsegmente
.stack folgt eine Größenangabe
.data folgt die Datendeklaration
.code folgt der Programmcode
BIT – Schaßan – WS 02/03
Assembler-Code-Struktur
.model small.stack 100h.data
…hier folgen Daten….code
Label:…hier folgt Code…END Label
BIT – Schaßan – WS 02/03
Beispiel-Prozessor 8086
BIT – Schaßan – WS 02/03
Fehlerhafte Anweisungen
MOV AX, BL AX hat 16 Bit, BL nur 8
MOV 122, AX Konstante kann kein Ziel sein
MOV AL, CFh zweideutige Anweisung: CFh könnte sowohl eine Hex-Zahl sein (=207), als auch eine Variable CFh
BIT – Schaßan – WS 02/03
Aufgaben des Betriebssystems
Ressourcenverwaltung:CPU (Rechenzeit)HauptspeicherFestplattenspeicherplatzexterne Geräte
Zentrale Bestandteile des Betriebssystems:ProzessverwaltungSpeicherverwaltungDateiverwaltung
BIT – Schaßan – WS 02/03
Dateiverwaltung
Was ist eine Datei? Inhalte als Folgen von Bits bzw. Bytes im Arbeits-, Festplattenspeicher, auf CD im Format name.erweiterungAngaben über Dateien werden vom Dateisystem verwaltet:
Name und TypLage und Länge im SpeicherZugriffsrechte
BIT – Schaßan – WS 02/03
Kataloge
Alle Informationen über Dateien finden sich in Katalogen (Verzeichnis, directory)Kataloge werden in Katalogen geschachtelt, es entsteht ein Dateibaum.Die Wurzel eines Baumes sind in DOS/Win Laufwerke.In UNIX gibt es eine Wurzel root, alle Laufwerke sind Teil des Baumes.
BIT – Schaßan – WS 02/03
Verwaltung der Kataloge
Unterscheidung zwischenbelegten Blöckenfreien Blöckenunzuverlässigen Blöcken
Verwaltung jeweils in einer Pseudodatei, die alle Blöcke einer Gruppe enthält
BIT – Schaßan – WS 02/03
Blöcke
Speichergeräte arbeiten blockweise, d.h. Blöcke fester Größe (normalerweise 512 Bytes) werden gleichzeitig und als eine Einheit aus dem Speicher gelesen oder darin abgelegt.In einem Katalog wird nur die Startadresse, d.h. der erste Block einer Datei und deren Gesamtgröße festgehalten.
BIT – Schaßan – WS 02/03
Dateioperationen
Neu: Anlegen einer leeren Datei mit einem Namen und Typ in einem bestimmten Katalog. Je nach Dateityp wird ein bestimmter Speicherbereich reserviert.Löschen: Zunächst wird nicht die Datei physikalisch gelöscht, sondern aus dem Katalog entfernt. D.h., der Verweis auf den ersten Block wird entfernt, aber erst wenn Teile der Datei physikalisch überschrieben werden, ist die Gesamtdatei tatsächlich unbrauchbar.
BIT – Schaßan – WS 02/03
Prozessverwaltung
Ein Programm, welches sich im Speicher befindet und vom Rechner bearbeitet wird, und alle dazugehörigen Ressourcen, heißt Prozess (engl. task).Hat ein Rechner genau eine CPU, so ist höchstens ein Prozess aktiv. Dieser wird als laufender Prozess bezeichnet.
BIT – Schaßan – WS 02/03
Zustandsdiagramm eines Prozesses
Von blockierten Prozessen müssen der Programm-code, seine Daten, der Inhalt der CPU-Register einschließlich Befehlszähler und eine Tabelle aller geöffneten Dateien im aktuellen Bearbeitungsstand gespeichert werden.
BIT – Schaßan – WS 02/03
Auslagerungsdatei
Wenn viele Prozesse gleichzeitig betrieben werden sollen, reicht evtl. der Arbeitsspeicher nicht aus, um die notwendigen Bereiche zur Verfügung zu stellen.Ein blockierter Prozess wird dann auf der Festplatte zwischengespeichert, d.h. ausgelagert.Für diesen Zweck reservieren Betriebssysteme feste Speicherbereiche als Auslagerungsdatei (swap space).
BIT – Schaßan – WS 02/03
Threads
Da Prozesse immer einen eigenen Speicher-bereich besitzen, hat man Threads eingeführt. Sie benötigen keinen eigenen Speicher. Wenn mehrere Threads gleichzeitig ablaufen, teilen sie sich den Speicherplatz.Moderne Programmiersprachen (Java, etc) haben Threads integriert.
BIT – Schaßan – WS 02/03
Prozessarten
Prozesse, die unabhängig voneinander ablaufen und nicht interagieren, heißen parallele Prozesse.Prozesse, die interagieren müssen kommu-nizieren (Daten oder Zwischenergebnisse austauschen). Ein System interagierender Prozesse heißt verteilt.
BIT – Schaßan – WS 02/03
Prozesskommunikation
Möglichkeiten der Kommunikation:synchron: die beteiligten Prozesse müssen je-weils an einer bestimmten Stelle im Programm-code angekommen sein. Falls notwendig, muss ein Prozess auf den anderen warten.Erst dann werden Daten ausgetauscht.asynchron: Wartezeiten werden vermieden
BIT – Schaßan – WS 02/03
Asynchrone Kommunikation
asynchron: Wartezeiten werden vermieden
shared memory: Speicherbereich wird für beide Prozesse zur gemeinsamen Benutzung freigegeben
Kommunikationskanal: ein Prozess sendet eine Botschaft in den Kanal, ein anderer Prozess kann sie empfangenDie Botschaften werden der Reihe nach gelesen, in der sie geschrieben wurden (FiFo = first in, first out)
BIT – Schaßan – WS 02/03
Kritische Bereiche
Greifen zwei Prozesse auf dieselben Bereiche zu, heißen die entsprechenden Codeabschnitte kritisch.Beispiel:
Prozess 1 Prozess 2MOV AX, size MOV AX, sizeINC size DEC sizeMOV size, AX MOV size, AX
BIT – Schaßan – WS 02/03
Kritische Bereiche (2)
Man muss garantieren, dass zwei Prozesse nicht gleichzeitig in ihrem kritischen Bereich sein können. Diese Forderung heißt wechselseitiger Ausschluss.Lösung 1: Der Prozess sendet ein interrupt disable Signal, sobald er fertig ist, ein interrupt enable.Problem: Funktioniert nur bei Betriebssystem-prozessen, nicht bei Benutzerprozessen, weil sonst der Benutzer die CPU lahm legen könnte.
BIT – Schaßan – WS 02/03
Kritische Bereiche (3)
Lösung 2: Einengung des kritischen Bereiches durch ProgrammiertricksBeispiel: test and set (TAS)<...unkritischer Bereich...>do { <TAS schloss, x> } while (x);<...kritischer Bereich...>schloss = false;
BIT – Schaßan – WS 02/03
Kritische Bereiche (4)
Lösung 3: Das Betriebssystem stellt Systemfunktionen bereit, die für andere Benutzerprozesse ununterbrechbar sind, da diese auf einer niedrigen Prioritätsstufe angesiedelt sind.Beispiel: Semaphore / Monitore
BIT – Schaßan – WS 02/03
Semaphore
Ein Semaphore (Signalmast) ist eine Datenstruktur bzw. Klasse mit einem Zähler count und den Methoden
wait() warte bis count > 0 und dekrementiere count
signal() inkrementiere count
Beispiel:<...unkritischer Bereich...>s.wait();<...kritischer Bereich...>s.signal();
BIT – Schaßan – WS 02/03
Semaphore (2)
Bei der Initialisierung von count wird festgelegt, wie viele Prozesse gleichzeitig im kritischen Bereich sein dürfen.Jedem Semaphore sollte eine Warteschlange zugeordnet werden. Eine erfolglose wait-Anweisung nimmt den Prozess in die Schlange derjenigen Prozesse auf, die auf das gleiche Semaphore warten.Ein signal entfernt den am längsten wartenden Prozess aus der Warteschlange.
BIT – Schaßan – WS 02/03
Monitore
Der Monitor ist eine Datenstruktur bzw. Klasse, von deren Methoden immer nur eine aktiv sein kann.Alle anderen Prozesse, die eine Prozedur des Monitors haben wollen, reihen sich in eine Warteschlange ein.Semaphore und Monitore sind gleich mächtig, das eine kann immer durch das andere implementiert werden.
BIT – Schaßan – WS 02/03
Deadlocks
Wenn zwei Prozesse gegenseitig auf ihre Ressourcen zugreifen wollen, kann es zum totalen Stillstand (deadlock) kommen.Bedingungen für einen Deadlock:
ringförmige Blockierung der Betriebsmittelkeine Möglichkeiten der Prozesse, dem anderen das reservierte Betriebsmittel zu entziehen
Lösungen:Ordnung der Betriebsmittel und Vorschrift, immer zuerst das in der Ordnung niedrigere zu belegenOrdnung der Prozesse (prozessID)
BIT – Schaßan – WS 02/03
Speicherverwaltung
Schutz vor Störung von Prozessen durch fehlerhafte Adressierung gemeinsam benutzter Speicherbereiche.Verfahren:
Swapping für Systeme mit realer Adressierung
Paging für Systeme mit virtueller Adressierung
BIT – Schaßan – WS 02/03
Swapping
Das Speicherabbild eines Prozesses besteht aus Segmenten unterschiedlicher Größe. Es ist ein bestimmter Speicherbereich, der voll-ständig im Arbeitsspeicher geladen sein muss, während der Prozess aktiv ist.Die Anzahl der Segmente ist meist klein, die Größe beliebig.
BIT – Schaßan – WS 02/03
Paging
Das Speicherabbild des Prozesses besteht aus Seiten (pages). Eine Speicherseite ist ein Segment vorgegebener Größe. Nur die benötig-ten Speicherseiten müssen im Arbeitsspeicher geladen sein, wenn der Prozess aktiv ist.Wird eine nicht geladene Seite adressiert, muss der Vorgang von der Hardware entdeckt werden.(Page fault) Der Prozessor muss dafür über eine virtuelle Adressierungstechnik verfügen. Die fehlende Seite wird dann vom Betriebssystem nachgeladen.
BIT – Schaßan – WS 02/03
Virtuelle Adressierung
BIT – Schaßan – WS 02/03
Bildung virtueller Adressen
Eine virtuelle Adresse besteht aus einem 12-Bit-Offset und einer virtuellen 20-Bit-Seite
BIT – Schaßan – WS 02/03
Virtueller Adressraum
Der virtuelle Adressraum, den ein Prozess angefordert hat, muss in der Paging Area reserviert werden.Zur Verwaltung des Adressraumes müssen Tabellen angelegt werden.Es gibt drei Arten virtuellen Adressraumes:
ohne entsprechendem Speicher, da bisher unbenutzt;auf Platte ausgelagerter, selten benutzter Speicherbereichreale Hauptspeicherseiten
BIT – Schaßan – WS 02/03
Bildung virtuellerAdressen (2)
Die virtuelle Seite wird in der Tabelle nachgeschlagen.Das Present/Absent-Bit zeigt an, ob eine Seite im Hauptspeicher vorhanden ist oder nicht.
BIT – Schaßan – WS 02/03
Bildung virtueller Adressen (3)
Gemeinsam bilden die Eintragung in die Seitentabelle und der Offset die reale 15-Bit-Speicheradresse.
BIT – Schaßan – WS 02/03
Virtuelle Adressierung (2)
Jeder Prozess darf alle Adressen verwenden, die aufgrund der Hardware möglich sind.Bei einem Rechner mit 32-Bit-Adressierung kann jeder Prozess einen Adressraum von 4GB verwenden, egal, wie groß der Arbeitsspeicher tatsächlich ist. Voraussetzungen sind:
Betriebssystem unterstützt virtuelle AdressierungBetriebssystem verwaltet den Hauptspeicher im Paging-VerfahrenProblem: die Festplatte muss groß genug sein!
BIT – Schaßan – WS 02/03
Seitenersetzung
Welche Seiten sollen ersetzt, welche im Arbeitsspeicher behalten werden?Bei der Verwaltung der Seiten besitzt (und benötigt) das Betriebssystem die folgenden Informationen:
wann wurde zuletzt auf eine Seite zugegriffen;wie häufig auf diese Seite zugegriffen worden ist;ob der Inhalt seit der letzten Zuweisung geändert worden ist;ob diese Seite hauptspeicherresident sein muss.
BIT – Schaßan – WS 02/03
Seitenersetzung (2)
Um möglichst wenig Seiten austauschen zu müssen, werden bestimmte Algorithmen angewandt, um z.B. vorherzusagen, wann oder wie oft eine bestimmte Seite benutzt werden wird.
Least Recently Used (LRU) Seite, die am längsten nicht benutzt worden ist, wird wahrscheinlich auch noch längere Zeit nicht gebraucht
BIT – Schaßan – WS 02/03
Seitenersetzung (3)
First in, first out (FiFo) die zuletzt geladene Seite wird ausgelagert, unabhängig davon, wann die Seite zuletzt angefordert wurdeRealisierung über einen Zähler in jeder Seite
BIT – Schaßan – WS 02/03
Seitenersetzung (4)
Wenn eine Seite seit dem letzten Laden nicht verändert worden ist, braucht sie nicht zurückgeschrieben werden. Nur wenn sie seit dem letzten Einlesen modifiziert worden ist, stimmt die Kopie nicht mit dem Inhalt des Hauptspeichers überein, die Seite muss aktualisiert werden.
BIT – Schaßan – WS 02/03
Interne Fragmentierung
Wenn ein Programm und Daten nicht genau den Raum voller Seiten einnehmen, bleibt am Ende einer Seite Platz übrig. Dieser leere Raum belegt dennoch Arbeitsspeicher, wenn eine Seite geladen wird. Man nennt dies interne Fragmentierung.
BIT – Schaßan – WS 02/03
Fragmentierung
Findet eine Datei beim Speichern auf Platte nach einer Veränderung nicht genügend Platz an ihrer ursprünglichen Stelle, so wird ein Teil an der ursprünglichen Stelle belassen, die restlichen Teile werden in anderen Blöcken abgelegt.Diese Teilung und Verstreuung von Dateien heißt Fragmentierung.
BIT – Schaßan – WS 02/03
Defragmentierung
Der Vorgang, verstreute Teile von Dateien wieder zusammen zu führen, heißt Defragmentierung.Man sollte in regelmäßigen Abständen die Festplatte eines Rechners defragmentieren, um den Zugriff auf die Festplatten zu beschleunigen.
BIT – Schaßan – WS 02/03
Literatur
Tanenbaum, Andrew S. / James Goodman: Computerarchitektur.Strukturen, Grundlagen, Konzepte.München: Pearson Studium, 2001.Darin: Kap. 6Tanenbaum, Andrew S.:Moderne Betriebssysteme. 2., verb. Aufl.München, Wien: Hanser, 1995.
Recommended