Zusammenfassung des Skript PDF

Preview

Summary

II. Information und bezeichnet den abstrakten Gehalt (Bedeutungsinhalt, Semantik) eines Dokuments, einer Anweisung, Nachricht oder Die Form der Darstellung (konkrete Form der Interpretation bezeichnet den nur gedanklichen) von der zur die Deutung der Gleiche Form kann verschiedene Interpretationen h...

Description

II. Grundlagen 1. Information und Repräsentation 

Information bezeichnet den abstrakten Gehalt (Bedeutungsinhalt, Semantik) eines Dokuments, einer Aussage, Beschreibung, Anweisung, Nachricht oder Mitteilung.  Die äußere Form der Darstellung heißt Repräsentation (konkrete Form der Nachricht).  Interpretation bezeichnet den (häufig nur gedanklichen) Übergang von der Repräsentation zur abstrakten Information -> die Deutung der Repräsentation. Probleme  Gleiche äußere Form kann verschiedene Interpretationen haben -> führt zu Missverständnissen  Nicht jede Repräsentation ist für jede Art von Verwendung zu gebrauchen -> maschineller Bereich, genaue Festlegung nötig  Information ist abstrakt -> Mensch kann Dinge in vielen verschiedenen Arten darstellen, aber der Computer braucht konkrete Menge Repräsentationen

2. Zahlensysteme 

Basis b jedes Zahlensystems legt die Wertigkeit einer einzelnen Stelle fest -> Dezimalzahlen haben Basis 10

 

 b bn-1 bn-2. . . b3 b2 b1 b0 größte darstellbare Zahl ist bn – 1 In der Informatik werden das Binär-, Hexadezimal-, und Oktalsystem verwendet

Binärsystem Binär-, Hexadezimal-, und Oktalsystem  Binärsystem: Basis 2 -> 2n verschiedene Ziffern darstellbar -> {0,1}  Oktalsystem: Basis 8 -> 8n verschieden Werte darstellbar -> {0,1,…, 7}  Hexadezimalsystem: Basis 16 -> 16n verschieden Werte darstellbar -> {0,1,…,9,A,B,C,D,E,F}  Grund für die Verwendung vom Binärsystem in Rechner: Es muss nur zwischen 2 Ziffern unterschieden werden Speicherbereiche in Rechnern 8 Bit ≙ 1 Byte

3. Binärdarstellung negativer ganzer Zahlen  

Da in Rechnern mit einer festen Länge an Ziffern gearbeitet wird, kann das 1 Bit für das Vorzeichen der Zahl verwendet werden -> darstellbare Zahlenbereich wird kleiner Je nach Darstellungsart entspricht das + der 0 oder 1 -> Meistens wird die 0 als + interpretiert

1-Komplement 

 

Weiteste am links stehende Ziffer gibt Vorzeichen an -> 0 = + Komplementbildung: Kippen der Ziffern Es gibt 2 nullen -> 0000 und 1111

2- Komplement

Exzess-Code



Komplementbildung: Kippen der Ziffern und anschließende Addition von +1



Verschieben eine Zahlenbereich ins positive, z.B. −128...−101... 127 um + 128 ins Positive

 

Es gibt nur eine Null -> 0000 Es gibt eine negative Zahl mehr wie positive



Es gibt nur eine Null, welche in der Mitte liegt Es gibt eine negative Zahl mehr wie positive





Darstellbarer Zahlenbereich: −2n−1 + 1 . . . 2n−1 − 1 Subtraktion: 1. Bestimmen des Komplements 2. Ergebnis durch Addition ermitteln 3. Wenn ein Übertrag entsteht, wird dieser durch eine Addition von 1 zum Ergebnis korrigiert



Darstellbarer Zahlenbereich: −2n−1 . . . 2n−1 − 1 Subtraktion: 1. Bestimmen des Komplements 2. Ergebnis durch Addition ermitteln 3. Übertrag kann ignoriert werden

Darstellbarer Zahlenbereich: −2n−1 . . . 2n−1 − 1 Addition: normale Addition und dann Verschiebefaktor abziehen 

Subtraktion: Komplement bilden => Exzess ist einfach das erste Bit vom 2er Komplement gekippt. Übertrag kann ignoriert werden

4. Darstellung von Daten und Zeichenketten ASCII-Codes – Zeichen und Zeichenketten  Erst Spalte dann Zeile -> 7 Bit zur Zeichen Repräsentation, 8. Bit Prüfbit oder auch „parity Bit“  Zur Fehlerkorrektur werden nur die parity Bits abgeglichen => gerade: p=0; ungerade: p=1  Darstellung von Zeichenketten: -> 1. Variante: Am Ende einer Zeichenkette ein Sonderzeichen (hier: NULL) -> 2. Variante: Vorangestellte Längenangabe

Darstellung von strukturierten Daten  Gleichartige Daten (Vektoren, Matrizen) werden in Anreihungen von Feldern und Spalten abgelegt (Array)  Padding: Kleinste adressierbare Einheit ist meist nicht 1 Bit sondern z.B. 4 Byte => Wenn Zeichenketten z.B. 5 Byte benötigen, werden die restlichen 3 mit Nullen aufgefüllt  Vorteil Padding: schnellerer Zugriff; Nachteil: Verschwendung von Speicherplatz Ablage im Speicher – Byte Reihenfolge  Little-Endian: kleinstwertigste Byte zuerst abspeichern -> Eine Zeichenkette würde also von links nach rechts abgespeichert werden, also so wie wir lesen  Big-Endian: höchstwertigste Byte -> Eine Zeichenkette würde also von rechts nach links abgespeichert werden, genau anders herum wie wir lesen. Deterministisch und determiniert  Deterministisch: Reihenfolge eindeutig festgelegt -> keine Wahlmöglichkeit  Determiniert: Ergebnis ist festgelegt -> für die Erzielung gibt es unterschiedliche Wege

III Betriebssysteme und von-Neumann Rechner 1. Betriebssysteme 

Betriebssystem soll Nutzung eines Rechners einfach machen und die Hardware effizient nutzen  Oftmals kommt es auf das Anwendungsgebiet des Systems an, ob der Schwerpunkt auf Effizienz oder Nutzerfreundlichkeit gelegt wird. Außerdem ist die Definition von Effizienz je nach Anwendungsgebiet unterschiedlich

Struktur von Betriebssystemen  Betriebssystem-Kern: Der Betriebssystem-Kern erfüllt die zentralen Aufgaben des BS => Scheduling etc.  Device-Treiber: Softwarebausteine, die die Integration von zusätzlicher Hardware in das BS erleichtern bzw. ermöglichen.  Erweiterte BS-Dienste: Stehen sowohl Programmen als auch Nutzern zu Verfügung und greifen auf Funktionen des BS zu, allerdings auf keine tiefergehenden Schichten.  Benutzerprogramme: Äußerste Schicht; nutzen die durch darunterliegende Schichten bereitgestellte Arbeitsumgebung  Aufteilung in Schichten hat zum Vorteil, dass Rechte vergeben werden können. Single Stream vs. Multiple Stream Single Stream Ein Programm behält die CPU solange, bis es entweder selbst andere Ressourcen anfordert oder selbst terminiert wird.  Nur freiwillige Freigabe der CPU  Kritisch bei nicht terminierenden Programmen

Multiple Stream Das BS verwaltet die CPU und vergibt diese nach „globalen Gesichtspunkten“  Voraussetzung: Ein Programm muss sinnvoll unterbrechbar sein, ohne das Ergebnisse verloren gehen

 Im Rahmen der Multiple Stream Verarbeitung entstand das Scheduling Batch Verarbeitung vs Interaktiv  Batch = Stapelverarbeitung: Nicht für Interaktion gedacht sondern möglichst hohen Durchsatz  Interaktiv: Sehr Benutzerfreundlich, da kurze Antwortzeiten => viel geringere Durchsatz (siehe Round Robin)

5. Rechnerarchitektur Komponenten eines Rechners Peripherie Geräte, Interne Speicher, Verarbeitungslogik, Steuerungslogik, Verbindungen Von Neumann Rechner   



Zentrale Komponenten: CPU und MEM (ROM+RAM) => interagieren über 2 Busse miteinander Datenbus: Transport der eigentlichen Daten zwischen CPU MEM und Peripherie Adressbus: Gibt Info welche Daten jeweils verschoben, gelesen und geschrieben werden

Unterteilung des MEM: 1. ROM: Read-Only-Memory: Hier befindet z.B. das BIOS 2. RAM: Random-Access-Memory: Kann frei adressiert werden => schreiben und lesen möglich  Programmierbarer Rechner, der für viele Zwecke eingesetzt werden kann  Probleme: Busse als Engpass und nicht so effizient wie vorherige Rechner, die spezifisch für einen Anwendungszweck entwickelt wurden

Aufbau einer CPU 





Datenprozessor Memory Buffer Register (MBR): 1. Lesen: Der Inhalt der Adresse des MAR wird in das MBR übertragen 2. Schreiben: Adresse im MAR gibt an wohin geschrieben wird, MBR überträgt den Inhalt an die passende Adresse.

  

 

Datenprozessor: Verarbeitet Daten und besteht hauptsächlich aus der Arithmetisch-Logische Einheit, in der Rechenoperationen, Vergleiche und einfache Veränderungen von Bits und Wörtern ausgeführt werden Befehlsprozessor: Grundlage für die Befehlsausführung, da hier der auszuführende Befehl analysiert (dekodiert) und Aufträge an die ALU gegeben werden, so wie auch das Holen des nächsten auszuführenden Befehl organisiert wird. Befehlsprozessor Memory Address Register (MAR): Kann genau eine Adresse speichern und interagiert mit dem MEM Arithmetisch logische Einheit (ALU): Führt die Berechnungen durch Akkumulator (A): Daten aus dem MBR werden zuerst in dieses Register geschrieben, bevor sie zur ALU gelangen Instruction Regsiter (IR): Hier liegt der aktuell ausgeführte Befehl Program Counter (PC): Enthält als Wert immer die Adresse des nächsten auszuführenden Befehls

Fetch-Execute-Zyklus 1. Fetch-Phase: Inhalt des PC wird ins MAR geladen. Der Befehlt wird dann via MAR vom MEM ins MBR geholt. Vom MBR wird er ins IR übertragen, wo er interpretiert wird 2. Excecute-Phase: Vom IR wird der Befehl zuerst mal decodiert. Nach der Dekodierung wird er von der ALU durchgeführt. Das entstehende Ergebnis wird im Akkumulator abgelegt. Der PC lädt nun die Adresse des nächsten Befehls Busse 

 

Serieller Bus Nur eine Datenleitung => heutzutage immer öfter eingesetzt, da die Leitungen immer leistungsfähiger werden Meist Verwendung zwischen Rechner und Peripheriegeräten, also auf großen Strecken USB = Universal Serial Bus

 

Paralleler Bus Mehrere Datenleitungen nebeneinander die jeweils 1 Bit übertragen Problem: Die Leitungen müssen synchron gehalten werden => auf langen Strecken problematisch

IV Schaltnetze und Schaltwerke 1. Aussagenlogik wahr = 1, falsch = 0 Konjunktion, Diskonjunktion und Negation Konjunktion AND

∧ bzw .

Liefert nur 1, falls beide den Wert 1 haben NAND, NOR und XOR NAND Nicht und

Diskonjunktion OR

Negation NOT

¬bzw . ‾

∨ bzw .+

Liefert nur 0 falls bei den Wert 0 haben

Dreh 0 zu 1 und 1 zu 0

NOR Nicht oder

XOR Entweder oder

Alles was mit aussagenlogischen Verknüpfungen ausdrückbar ist, ist mit NOR oder NAND ausdrückbar => Vereinfacht die Hardware-Realisierung da nur NAND bzw. NOR realisiert werden muss. Rechengesetze  Wenn es verschachtelte Funktionen gibt, wird von innen nach außen aufgelöst  Es gelten: kommutativ, assoziativ, distributiv  De Morgan: ¬ ( x y ) =( ¬ x ∨ ¬ y )

2. Darstellung boolscher Funktionen  

Jede Funktion deren Ein- und Ausgaben sich binär auf endlicher Länge darstellen lassen, kann auch durch eine boolesche Funktion mit entsprechender Tabelle dargestellt werden. n m B ⟶ B => n-stellige boolsche Funktion mit n Eingaben und m Ausgaben

„Disjunktion von Mintermen“ und „Konjunktion von Maxtermen“ DNF (Mintterme) KNF Darstellung aller Argumentkombinationen mit 1 Darstellung aller Argumentkombinationen mit 0 Minterm: Macht passende Variablen alle zu 1, z.B.: Maxterm: Macht alle passenden Variablen zu 0 0001: Disjunktion von Mintermen: Konjunktion von Minttermen: Sobald einer der Mintterme 1 ergibt, ist die ganze Disjunktion 1

Sobald einer der Maxterme 0 ergibt, kommt eine 0 raus

3. Realisierung boolescher Funktionen durch Schaltnetze

4. Typische Schaltnetze mit Steuerungsfunktion Multiplexer  2d verschiedene Eingänge mit d Steuereingängen und 1 Ausgang  Der Wert der Auf den Steuerleitungen anliegt, entscheidet darüber welches der Eingangssignale weitergeleitet wird => Binärzahl der Steuerleitung gibt an die wievielte Leitung weitergegeben werden soll  Hier dienen die Und-Bausteine als Schalter, denn Sie geben nur ein Signal (also eine 1) weiter, wenn alle Eingangssignale 1 sind

De-Mulitplexer  2d Ausgänge, d Steuerleitungen und 1 Ausgang =>  Spezialfall des De-MUX: Decoder => hat keinen Eingang und gibt immer eine 1 auf einer Ausgangsleitung weiter  Decoder adressiert eine bestimmte Leitung Encoder  Gegenstück zum Decoder => gibt die Nummer der belegten Leitung des Decoders aus  Es sind nur Eingaben mit genau einer 1 erlaubt, da der Decoder auch nur eine 1 ausgibt und sonst nur 0 1 Bit Halbaddierer  Nur bei 1 + 1 entsteht ein Übertrag, sonst ist der Übertrag, Carry genannt, 0  Die Addition entspricht einem XOR Baustein, der Übertrag entspricht einem UND Baustein  Problem: Halbaddierer kann nur Übertrag erzeugen, aber nicht darauf reagieren 1-Bit Volladdierer  Hat noch einen dritten Eingang für das Carry in  Berechnet die Ergebnissumme schrittweise durch zweimaliges Nutzen des XOR-Bausteins  Durch nacheinander Schalten dieser 1-Bit Addierer entstehen zum Beispiel 4-Bit Addieren

5. Schaltwerke als Schaltnetze mit Rückkopplung 

Schaltwerk = Schaltnetz mit mindestens 1 zyklischen Verbindung



Um die Rückkopplung zu kontrollieren, gibt es eine Sperre zwischen Vorspeicher und Speicherzell Takt nicht gesetzt = Sperre verschlossen und Zeit um den Wert aus S als Eingabe in OR zu nutzen und



einen anderen Wert in V zu legen  Takt gesetzt = Sperre offen, Wert wird von V nach S verschoben  Ausgabe ist hier abhängig vom Wert aus S => Ein Wert wird in S gespeichert Latches  S = Set, R = Reset; Q und Q quer  Speichern einen stabilen Zustand NOR-Latch  

NAND-Latch 1 Setzten = Q nimmt den Wert 1 an 0 Setzen = Q nimmt den Wert 0 an

V. Prozesse und Ressourcen in Betriebssystemen 1. Prozesse aus Sicht des Betriebssystem Prozess  Aktionsfolge die durch die Ausführung von Programmen entsteht  Systemprozess: Teile des BS die Zugriff auf alle Teile des Systems haben  Benutzerprozess: Haben keinen Einblick in das Gesamtsystem => Sicherheitsgründe! Prozesszustände: BS weist die Prozesszustände zu NEW 



ACTIVE

TERMINATED

Für jeden READY RUNNING WAITING Prozesszustand gibt es Prozess hat alles, was er Prozess wird gerade auf der Prozess wartet auf eine eine eigene braucht, nur nicht die CPU, CPU ausgeführt. Ressource, die er auf die er wartet. angefordert Warteschlange => hat (z.B. I/O) WAITING gibt es je nach Ressource nochmals weitere Warteschlangen Eigentlich steht nicht der Prozess an sich in der Warteschlange, sondern der Process Control Block (PCB) des jeweiligen Prozesses

Von Ready zu Running  BS bereitet Wechsel vor, indem es wichtige Programmteile in den Hauptspeicher lädt  Scheduler: Entscheidungsträger, wer wann die CPU erhält  Dispatcher: Führt Prozesswechsel durch => speichert Daten des gestoppten Prozess + lädt Daten des neuen Prozesswechsel  Non-Preemptive Scheduling: Interrupt nicht möglich => Prozess wird, sofern er keine weiteren Ressourcen braucht von Anfang bis Ende durchgeführt (Run to completion)  Preemptive Scheduling: Unterbrechung eines Prozess möglich (interrupt) => Running -> Ready  Bei Interrupt wird der aktuelle Zustand des Prozesses im Process Control Block gespeichert  Oftmals hoher Overhead bei schwergewichtigen Prozesswechseln: Schlechtes Verhältnis von Abarbeitung und Verwaltung  Context-Switch: Zeit die gebraucht wird um einen Prozess auszulagern und einen neuen einzulagern Optimierung von Prozesswechseln: (für genaues Beispiel siehe Skript S. 187)  Task (schwergewichtiger Prozess) wird unterteil in mehrere Threads (leichtgewichtig)  2 Threads vom gleiche Task haben fast den gleichen PCB, sodass ein Wechsel dieser Threads schnell durchzuführen ist.  Durch bilden von Threads kann ein Prozess von mehreren CPUS gleichzeitig bearbeitet werden

2. CPU Scheduling Verfahren Bewertung der Scheduling Verfahren  Idle-Zeit: CPU hat nichts zu tun, obwohl etwas zu tun wäre => Aus Gesamtsystemsicht: gering halten  Turn-around-Zeit: Zeit vom Abschicken des Auftrags bis zu Beendigung => Aus Prozesssicht: gering halten  CPU-Burst: Zeit der CPU-Nutzung eines Prozesses (Rechenzeit)  Serversysteme ohne Interaktion: viel Durchsatz => wenig Idle-Zeit (meist Batch-Systeme = Stapelverarbeitung)  Interaktive Systeme: schnelle Antwort auf Eingabe => viel Idle-Zeit, da Zeitscheibenverfahren

Scheduling Verfahren First-Come-First-Serve (FCFS) Non-preempitve Abarbeitung nach Reihenfolge der Ankunft => komplett faires Verfahren

Shortest-Job-First (SJF)

Non-preempitve Immer wenn die CPU frei ist, wird der Prozess mit der kürzesten Bearbeitungszeit genommen. Bei gleichen Zeiten gilt FCFS.

Shortest-RemainingProcess-Time-First (SRPTF) Preemptive Wenn neuer Prozess reinkommt, wird dessen Bearbeitungszeit mit der verbleibenden des laufenden Prozesses verglichen. Wenn diese kürzer ist, findet ein Prozesswechsel statt.

Round-Robin Scheduling (RR) Preemptive Festlegung einer Zeit die jeder Prozess hat, danach wird gewechselt. Welcher Prozess als nächstes drankommt wird mit FCFS festgelegt.

SystemprozessVerwendet Warteschlange Verwendet in Warteschlange und für Prozesse die mit Batch Warteschlange für Cluster (Nutzung freier verarbeitet werden (z.B. Prozesse mit Interaktion Ressourcen für Simulation Virenscanner) etc.  In der Praxis werden mehrere Warteschlangen je nach Prozesstyp (System, Interactive, Batch, Cluster) gebildet und in diesen verschiedene Verfahren angewandt (-> siehe letzte Zeile Tabelle; weiter Ausführungen, wie man das Verfahren noch fairer gestaltet siehe Skript S. 201f) Scheduling mit Prioritäten  Festlegung von Prioritätsklassen (z.B. nach Herkunft, Prozessart etc.)  Einfache Prioritätssteuerung: Erst alle Prozesse mit höchster Priorität abarbeiten, falls es dort mehrere mit der gleichen gibt, dann wird z.B. nach FCFS vergeben (siehe Tabelle letzte Zeile)  Dynamisches Verfahren: Berücksichtigung der bisherigen Wartezeit => je länger der Prozess wartet, desto höher wird die Priorität (genaue Formel Alterungsprinzip siehe Skript S. 198)  Multi-Level-Feedback-Queues (siehe Skript S. 202)

3. Ressourcevergabe in Betriebssystemen Ressource  Physikalische Ressourcen: CPU, MEM, I/O-Geräte  Logische Ressourcen: Schreibberechtigung für eine Datei, Teilergebnis einer Berechnung etc.  Ein Prozess ist eine Folge von Ressource-Nutzungen  Zugriffsdisziplin eines Prozesses auf Ressourcen: Request – Wait – Hold – Release Deadlock Ein Deadlock entsteht beim gleichzeitigen Vorliegen der folgenden vier Bedingungen: 1. Eine Ressource wird exklusiv benötigt (Ein Prozess hält die ganze Ressource) 2. Die Ressource auf die gewartet wird, hält ein andere Prozess 3. Eine Auflösung (des hold) durch Unterbrechung ist nicht Vorgesehen 4. Die Warte-Beziehung unter Prozessen des Deadlocks ist zirkulär  Bei Desktop Systeme werden Deadlocks einfach ignoriert, aber bei anderen wichtigen Systemen (z.B. Transaktion) gilt es Deadlocks zu vermeiden Permanente Blockierung  Ein Prozess wartet auf einen Ressource, ohne die er nicht ausgeführt werden kann  Der andere Prozess, der diese Ressource hält, gibt diese nicht frei (aufgrund eines Fehlers etc.)  Unterschied zum Deadlock: Deadlock ist eine zyklische Blockierung => die Prozesse halten jeweils die Ressourcen die der andere zum Fortfahren braucht

Starvation  Ein Prozess könnte zwar weitergeführt werden, aber aufgrund unfairer Vergabeentscheidungen des BS kommt er nicht zum Zug  Starvation kann auch bei unfairen CPU-Scheduling Verfahren eintreten => Die CPU ist im Prinzip auch nur eine Ressource Einfaches Ressourcen-Modell  Ausgangspunkt: System mit verschiedenen Ressourcentypen {R1, . . . , Rm} => Jeder Typ hat mehrere Instanzen, heißt er wird nochmals aufgeteilt, sodass er von mehreren Prozessen gleichzeitig genutzt werden kann  Prozesse werden so dargestellt: P1, . . . , Pn Vektor Bedeutung Pn: Request(Rj,k) Prozess n fordert k Instanzen vom Ressourcentyp Rj an Pn: Release(Rj,k) Prozess n gibt k Instanzen vom Ressourcentyp Rj frei ALLOCATEi

¿

die Pi von R 1 hält ( ¿¿Instanzen Instanzen die Pi von Rj hält )

Gibt Auskunft darüber wie viele Instanzen ein Prozess von jedem Ressourcentyp aktuell hält Needsi ¿

die Pi noch von R 1 benötigt ( ¿¿ Instanzen Instanzen die Pi noch von Rj benötigt )

Gibt Auskunft darüber wie viele Instanzen dem Prozess Pi von jedem Ressourcentyp noch fehlen Maxi ¿

die Pi von R 1 maximal benötigt ( ¿¿Instanzen Instanzen die Pi von Rj maximal benötigt )

Gibt Auskunft darüber wie viele Instanzen ein Prozess von jedem Re...