Kapitel 3 - 5

Logik-Ausssage für “Oder-Verknüpfungen”; Zeichen ∨

Venn-Diagramm von A ∨ B

Logik-Aussage für Und-Verknüpfungen; Zeichen ∧

Venn-Diagramm für A ∧ B

• F:B^n -> B^1

• alle Kombinationen aus n-true/false Werten jeweils einem einzelnen true/false Wert zuordnet

1) alle Kombinationen aus B^n als Tabelle aufstellen

2) Bedingung/Formel formulieren

3) Ergebnisse der Bedingung in Spalte y notieren; 1 entspricht Bedingung erfüllt, 0 entspricht Bedingung nicht erfüllt

• normierte Funktionsdarstellung boolscher Algebra

• Konjunktionen von Disjunktionen über alle Variablen

• Erstellung

  • Für alle Zeilen der Wahrheitstabelle mit Ergebnis = 0 werden Disjunktionen aufgestellt

  • Disjunktionen werden durch Konjunktionen verbunden

• normierte Funktionsdarstellung boolscher Algebra

• Disjunktion von Konjunktionen über alle Variablen

• Erstellung

  • Für alle Zeilen der Wahrheitstabelle mit Ergebnis = 1 werden Konjunktionen aufgestellt

  • Konkunktionen werden durch Disjunktionen verbunden

Kommen in einer disjunktiven Form (DF) zwei Konjunktionen vor bzw. kommen in einer konjunktiven Form (KF) zwei Disjunktionen vor, die sich in genau einer komplementären Variablen unterscheiden, dann können diese durch den gemeinsamen Teil ersetzt werden.

a) Eine Abbildung f : B^n → B^m heißt Schaltabbildung (Für m=1 heißt f Schaltfunktion.)

b) Die Darstellung einer Schaltabbildung durch Gatter bezeichnet man als Schaltnetz (oder Schaltkreis).

Addition zweier einstelliger Dualziffern x,y mit Beachtung des Übertrags

Addition zweier Dualziffern x,y und einlaufendem Übertrag u

1. Arbeitsphase:

• Inhalt von S wird (nach rechts) abgegeben → steht als Signal y_i für längere Zeit zur Verfügung

• Ein Signal x_i wird in V gespeichert

• V und S sind durch eine Sperre getrennt

2. Setzphase:

• durch zentral erzeugte Taktimpulse wird Sperre kurzzeitig aufgehoben, Inhalt wird von V zu S gegeben

• es werden keine Signale x_i aufgenommen bzw. Signale y-i abgegeben.

• Speicherprogrammierung (Universalrechner): Struktur des Rechners unabhängig von der zu bearbeitenden Aufgabe; Bearbeitungsvorschrift (Programm) wird für jede Aufgabe eingegeben und im Speicher abgelegt

• Gleichheit von Daten und Programmen: Ablage in einheitlichem Speicher, d.h. Programme sind auch Daten

• Adress-Speicherung: Jeder Speicherplatz erha ̈lt eine numerische Adresse; Daten sind u ̈ber diese Adresse abrufbar

• Sequentielle Programmspeicherung: Einzelschritte der Bearbeitungsvorschrift werden in aufeinander- folgenden Speicheradressen abgelegt;  Bestimmen des na ̈chsten Befehls −→ erhöhe Adresse des aktuellen Befehls um 1;

• Verfügbarkeit von Adress-Sprüngen: Sprungbefehl: Operand dieses Befehls enthält Adresse des nächsten Befehls

• Verfügbarkeit bedingter Sprungbefehle: Nach Ausführung des aktuellen Befehls (Adresse a) wird mit dem Befehl aus Adresse b != a + 1 fortgesetzt falls Bedingung p erfüllt ist → Programmablauf von Zwischenergebnissen abha ̈ngig

• Rechenwerk: Rechenoperationen wie z.B. Addition, Multiplikation – logische Verknüpfungen wie z.B. ODER, UND

• Steuerwerk (Leitwerk) – Interpretiert Programmbefehle: steuert Ausführung der Befehle

• Speicher; enthält Daten und Programme; schneller Zugriff

• Ein-/Ausgabe: einlesen und ausgeben von Daten/Programmen

• AR: Allgemeine Register für Operanden und Ergebnisse

• ALU: Arithmetisch-Logische-Einheit

• SPR: Speicher-Puffer-Register kommuniziert mit dem Speicher

• BR: Befehlsregister enthält aktuellen Befehl

• PZ: Programmzähler enthält Adresse des nächsten Befehls

• SAR: Speicher-Adress-Register enthält Adresse des nächsten Speicherzugriffs

  
  

Umso schneller der Speicher, umso tuerer. Speicherhierarchie ist Organisation des Speichers für einen kosteneffizienten Aufbau.

• Prozessverwaltung: Zuteilung von CPU, wenn mehrere Benutzer an einem Rechner arbeiten

• Speicherverwaltung: Speicherzuteilung, Speicherfreigabe, Schutz des Speichers vor unerlaubtem Zugriff, Bereitstellung von Speicher außerhalb des Arbeitsspeichers (virtueller Speicher).

• Dateiverwaltung: Strukturierung eines Dateisystems (Verzeichnisse, Dateinamen), Zugriffsrechte.

• (Ein-/Ausgabesteuerung: Zuteilung von Ein-/Ausgabegeräten zu Prozessen (Instanzen von Programmen).)

• (Netzwerkverwaltung: Eingehende Datenpakete sammeln und an zugehörigen Prozess weiterleiten, ausgehende Daten verpacken und versenden.)

Programm: Abfolge von Befehlen

Prozess:

• konkrete Instanziierung eines Programms zu dessen Ausführung

• ergänzt mit zugehörigen Daten im Arbeitsspeicher und Registerinhalten (nsbesondere PZ)

• zu einem Programm kann es gleichzeitig mehrere Prozesse geben

Non-Präemptives Scheduling:

• First-In-First-Served: zuerst gestartet, wird zuerst abgearbeitet, aber ewig laufender Prozess blockiert

• Last-in-First-Served

• Präemptives Scheduling: jeder laufende Prozess erhält eine Zeit zugewiesen

• Round-Robin-Scheduling: Warteschlange wird nacheinander abgearbeitet

• Prioritätenbasiertes Scheduling: Prioritäten werden in der Warteschlange vergeben

• Multilevel Feedback Queue Scheduling: Kombination aus Prioritätsbasiertem Scheduling und Round

sich periodisch wiederholende Nutzungszuteilung einer Ressource für eine festen Zeitabschnitt

Priorität gibt Dringlichkeit der Abarbeitung wieder

• jeder Prozess bekommt Priorität zugewiesen

• Prozess mit höchster Priorität darf laufen

• Prozess mit niedriger Priorität kommt selten bzw. nie dran

statische Prioritäten:

• höchste Priorität: BS-Prozesse

• nächst höchste Priorität: Interaktive Prozesse

• niedrigste Priorität: Hintergrundprozesse

dynamische Prioritäten:

• lief ein Prozess bereits längere Zeit: Priorität wird erniedrigt

• war ein Prozess lange blockiert: Priorität wird erhöht

Scheduling-Verfahren

Vorgehen:

• Liste von Prozessen werden von BS verwaltet

• Prozesse erhalten nacheinander während eines Zeitschlitzes (Ablauf einer Zeitscheibe) Zuteilung auf ausführende CPU

• Prozess wird nach Ablauf des Zeitschlitzes unterbrochen und am Ende der Liste einsortiert

• nächst-oberster Prozess erhält Zuteilung auf ausführende CPU

• neu hinzukommende Prozesse werden am Ende der Liste eingefügt

• Blockiert ein laufender Prozess, so wird er ausgelagert und nach Beendigung der Blockade ans Ende der Liste eingefügt

  • (Blockade z.B. Warten auf Terminaleingabe, Warten auf Zuteilung des Druckers)

Scheduling-Verfahren

• neuer Prozess wird am Ende der obersten FIFO-Warteschlange eingefügt.

• Prozess an vorderster Stelle in höchstpriorisierter nichtleerer Warteschlange wird als erstes bearbeitet

• vollständig abgearbeiteter Prozess, verlässt das System

• blockierter Prozess kann Prozessor vor Ablauf der Zeitscheibe abgeben (z.B. wegen fehlender Eingabe), die Warteschlange wird verlassen.

  • Wenn Blockade aufgehoben ist, wird er am Ende derselben Warteschlange eingereiht

• Prozess, der die gesamte Zeitscheibe in Anspruch nimmt, wird unterbrochen und an das Ende der nächstniedrigen Warteschlange gesetzt.

  • War er bereits in der niedrigsten Warteschlange, dann wird er dort wieder ans Ende gesetzt.

(TBD)

• Simulation von sequentiellen Prozessen im Arbeitsspeicher

• virtuell existiert für jeden Prozess ein zusammenhängender Bereich, physikalisch sind die Prozesse auf unterschiedlichen Bereichen

• Prozesse die größer als der Arbeitsspeicher sind können bearbeitet werden, da Prozesse auch im Hintergrundspeicher liegen können

  
  

• lagere Seite aus mit Access-Bit=0 ∧ Modified-Bit=0

(Seite wurde in letzter Zeit nicht gebraucht und liegt unvera ̈ndert im Hintergrundspeicher → kein Kopieren)

• lagere Seite aus mit Access-Bit=1 ∧ Modified-Bit=0

(Seite wurde zwar gelesen muss aber nicht in den Hintergrundspeicher kopiert werden)

• lagere Seite aus mit Access-Bit=0 ∧ Modified-Bit=1

(Seite wurde in letzter Zeit nicht gebraucht, d.h. wurde auf 0 zuru ̈ck- gesetzt, wurde fru ̈her jedoch modifiziert → muss in den Hintergrund- speicher kopiert werden)

• Informationen logische Adresse: Seitennummer, Offset

• Informationen Seitentabelle (je Prozess):

  • les- und /oder schreibbar

  • Basisadresse

  • V-Bit (befindet sich im physikalischen Speicher

  • Access-Bit: zuletzt lesender/schreibender Zugriff

  • Modified-Bit: wurde geändert

• einfache nichtflüchtige Lagerung von Daten und Programmen (Dateien)

• auf persistenten (dauerhaften) Speichermedium wie Festplatte oder Stick

• Nutzer muss sich nicht um Verwaltung kümmern

• Dateisysteme sind heutzutage hierarchisch aufgebaut

• effiziente Nutzung des vorhandenen Speicherplatzes

(dieser ist — wie im vorangegangenen Abschnitt motiviert in — Blöcke fester Größe aufgeteilt, um den schnellen Datentransfer zum Arbeitsspeicher zu gewährleisten)

• schneller Dateizugriff auch auf sehr große Dateien

• zusammenhängende Belegung: Daten einer Datei liegen hintereinander, daher schnellster Zugriff; Belegung aber kompliziert (Problem der Fragmentierung)

• Verkettete Belegung: Daten referenzieren auf unzusammenhängende Blöcke, aber Sprünge sind aufwändig

• inodes: hierarchische Datenstruktur (siehe eigene Karteikarte)

Besteht aus

• Metadaten

• 12 Adressen die direkt auf Blöcke verweisen

• 13. Adresse verweist auf einfachen Adressblock, Adressblock bestehend aus 256 Adressen

• 14. Adresse auf Verweisblock, der auf zwei Adressblöck verweist

Block bit maps - Verwaltung von freien und belegten Blöcken