Technische Grundlagen 1 - Q1

- 2 Prozesse haben je einen Druckauftrag

- Queue arbeitet mit Ringpuffer und 2 Zeigern

- A liest Zeiger x für nächsten freien Druckauftrag aus, anschließend Unterbrechung von A

- B liest ebenfalls Zeiger (immer noch x) aus und trägt dort Datei mit Druckauftrag ein

- Aktivierung von A, A fährt fort, indem er seinen Druckauftrag in Ringpuffer an Stelle x schreibt

--> Druckauftrag von B wurde überschrieben

Abschnitte eines Programms, in denen gemeinsam genutzter Speicher verwendet wird --> es sollte verhindert werden, dass dies durch zwei oder mehr Prozesse quasi gleichzeitig geschieht

TSL-Anweisung (test and set lock)

Sleep and Wakeup

Semaphoren (Dijkstra)

- Einführung einer unteilbaren (!) Hardware-Anweisung, die eine Speicherstelle LOCK ausliest, dessen Inhalt in Register RX ablegt und in der Speicherstelle LOCK einen Wert ungleich 0 ablegt

- jeder weitere Prozess, der auf Speicherstelle zugreifen will, macht das ebenso und vergleicht, ob in RX eine 0 steht

- da das nicht der Fall ist, solange der erste Prozess nicht fertig ist und wieder eine 0 in LOCK abgelegt hat, kann er nicht mit dem Zugriff auf die Speicherstelle fortfahren, sondern wiederholt den Vergleich - bis der erste Prozess fertig ist

- Nachteil der TSL-Anwendung: aktives Warten, Verschwendung von Rechenzeit

- Einführung zweier Systemaufrufe: Sleep (blockiert Prozess) und Wakeup (Aufheben der Blockade)

- Wakeup benennt den aufzuweckenden Prozess ODER Sleep und Wakeup nutzen gemeinsame Speicheradresse

- Semaphore = spezielle Ganzzahl-Variable

- Definition von zwei unteilbaren Operationen Down und Up

- Down: Prüfe, ob Wert > 0. Ja: Erniedrigen des Wertes um 1 und fortfahren. Nein: Unterbrechen wie bei SLEEP

- Up: Prüfe, ob wartende Prozesse für Semaphore vorhanden. Ja: Aufwecken eines Prozesses (wie WAKEUP). Nein: Erhöhen der Semaphore um 1.

- Beim Aufruf der Funktion wird Wert der Variable überprüft. Bei 0 wird Prozess das Betreten des kritischen Abschnittes, bzw. die Belegung des Betriebsmittels verweigert.

"Menge von Prozessen befindet sich in einem Deadlock, wenn jeder Prozess aus der Menge auf ein Ereignis wartet, das nur ein anderer Prozess aus der Menge auslösen kann." (Tanenbaum)

- wechselseitiger Ausschluss (Rssource entweder verfügbar oder genau einem Prozess zugeordnet)

- Hold-and-Wait-Bedingung (Prozesse mit reservierten Ressourcen dürfen weitere anfordern)

- Ununterbrechbarkeit (reservierte Ressourcen können nicht entzogen werden)

- zyklische Wartebedingung (jeder Prozess wartet auf eine Ressource, die dem nächsten in einer Kette gehört)

- Deadlocks erkennen und beseitigen

- Deadlocks verhindern durch vorsichtiges Ressourcenmanagement

- Deadlocks unmöglich machen durch Abschaffen min. einer Voraussetzung

- Deadlocks ignorieren (Vogel-Strauß-Algorithmus)

eine Ressource pro Ressourcentyp:

- Nutzung eines gerichteten Graphen, von dem Prozesse, die bereits eine Ressource belegen, und Prozesse, die Ressourcen anfordern, abhängig sind

- beim Auftreten von Zyklen in dem Graph --> Deadlock entstanden, beteiligte Prozesse und Ressourcen können identifiziert werden

- Unterbrechung und temporäre Freigabe

- teilweises Wiederholen

- Prozessabbruch

- Suspendieren des Prozesses mit der kritischen Ressource

- Nutzung der nun freien kritischen Ressource durch den zweiten Prozess

- anschließende Wiederzuordnung der Ressource zum ersten Prozess

- regelmäßiges Schreiben von Checkpoints

- bei Auftreten eines Deadlocks Zurücksetzen bis zu dem Checkpoint, zu dem der Prozess die kritische Ressource noch nicht hatte

Schrittweises Abbrechen verklemmter Prozesse bis zur Beseitigung des Deadlocks (Extremfall: Abbrechen aller Prozesse)

- maximales Ressourcenlimit

- Bedienung von Anfragen nach Ressourcen nur, wenn kein Deadlock vorliegt und es eine Reihenfolge gibt, die nicht zum Deadlock führt

- Beispiel:

Prozess A hat 3 und braucht 9 Ressourcen, B hat 2 und braucht 4, C hat 2 und braucht 7

3 Ressourcen sind noch frei

--> A und C können mit den 3 Ressourcen nicht zu Ende arbeiten, daher bekommt B sie

- Verhindern von wechselseitigem Ausschluss (im Allgemeinen nicht möglich)

- Verbieten zusätzlicher Betriebsmittelanforderungen

- Wiederherstellung der Unterbrechbarkeit (z.B. durch Ressourcenentzug, nicht immer praktikabel)

- Verhindern vom zyklischen Warten (z.B. durch Festlegen einer linearen Ordnung aller Betriebsmittel, Finden vernünftiger Ordnung jedoch kaum möglich)

- nur seltenes Auftreten von Deadlocks

- sehr hohe Kosten für Verhinderung, Erkennung und/oder Beseitigung von Deadlocks

- Abwägung zwischen Korrektheit und Bequemlichkeit

Complex Instruction Set Computer

- viele, mittels Mikroprogramm und Interpreter realisierte Instruktionen

- großer Befehlsumfang und komplexe Adressierungsmöglichkeiten

Reduced Instruction Set Computer

- wenige, dafür vollständig in Hardware implementierte Instruktionen

- Beschränkung auf wirklich notwendige Befehle

- Schaltungs- und Steuermaßnahme, die über spezielle Datenleitungen auf dem Motherboard eine Verbindung zwischen Erweiterungen/Peripherie und dem Arbeitsspeicher herstellt --> Schreiben der Daten direkt in den Speicher, ohne Umweg über den Prozessor

- Nutzung bei Ein-/Ausgabegeräten, die Daten mit hoher Geschwindigkeit übertragen können

- Problem: DMA-Controller konkurrieren mit dem Prozessor um Bus- und Speicherzugriff

- Mensch-Maschine-Interaktion (Eingabe, Ausgabe von Informationen)

- Datenstrukturen (Speicherung)

- Rechnernetze (Transport)

- Algorithmen (Manipulation)

Lösungstabellen, ABAKUS, Rechenschieber

1.) erste urkundlich erwähnte Rechenmaschine (1623)

2.) Rechenmaschine für Addition und Subtraktion (1642)

3.) Rechenmaschine mit 4 Grundrechnenarten (1673)

4.) "Analytical Engine", erste programmierbare Rechenmaschine mit Speicher, Recheneinheit, Ein- und Ausgabeeinheit (1833)

1.) "Z3", erste frei programmierbare Rechenmaschine mit Hilfe von Relais (1941)

2.) "ABC", Rechenmaschine mit Binärarithmetik und Speicher mit Kondensatoren (1941)

3.) "Mark 1" (1944)

1.) "COLOSSUS", erster elektronischer, digitaler Computer, unterstützte ENIGMA-Nachrichten-Entschlüsselung (1943)

2.) "ENIAC", Electronic Numerical Integrator and Computer (1946)

1.) "TX-0", erster mit Transistoren bestückter Computer (1955)

2.) "PDP-8", erster Computer mit einem Omnibus: Verbindung der Komponenten des Computers (1964)

3.) "6600er" erster Computer mit mehreren parallelen Funktionseinheiten, z.B. für Addition, Multiplikation (1964)

- auf integrierten Schaltungen (dutzende Transistoren auf einem Chip) basiert

- Ausführung der gleichen Programme auf Modellen unterschiedlicher Leistung möglich

- Einführung des Mehrprogrammbetriebs

- Emulation/Simulation anderer Computer

Etwa alle 18 Monate verdoppelt sich die Anzahl der Transistoren von integrierten Schaltungen (2012 Größenordnung 10^9).

Symbole/Signale --> Syntax (Aufbau) --> Daten

Daten --> Semantik (Bedeutung) --> Information

Information --> Pragmatik (Zweckbezug) --> Wissen

Information, Eingabe --> (Repräsentation) --> Eingabedaten --> (Datenverarbeitung) --> Ausgabedaten --> (Abstraktion/Interpretation) --> Information, Ausgabe

Bit = kleinste Dateneinheit, zwei mögliche Zustände (0 oder 1)

Bitfolge der Länge n hat 2^n Bitfolgen, Byte hat damit 2^8 = 256 Bitfolgen

(eindeutige) Abbildung einer Information auf die vom Computer verständliche Form von Bitfolgen

American Standard Code for Information Interchange

7 Bits (max. 128 Zeichen: 52 Buchstaben, 10 Ziffern, 4 Satzzeichen - damit reichten 6 Bit nicht mehr aus)

heute: Basis für verschiedene Erweiterungen wie z.B. deutsche Umlaute

früher: Kontrollbit

- internationaler Standard, um sämtliche Zeichen unterschiedlicher Kulturkreise in einem digitalen Code unterzubringen

- jedes Zeichen hat eigene Nummer, system-, programm- und sprachunabhängig

- Unicode Transformation Format: Codierung für Unicode-Zeichen

- UTF-8: ASCII-Zeichen in 8 Bit, freie Bitfolgen durch 8. Bit als Präfix genutzt, um anzuzeigen, dass noch weitere Bit folgen

- UTF-16: die meisten der existierenden Zeichen in 16 Bit

- UTF-32: alle Zeichen in 32 Bit

BMP, GIF, JPEG

- SVG

- Computerschriften

- Informationen zu jedem Bildpunkt gespeichert

- Anzahl Bit pro Bildpunkt von Genauigkeit der Farbdarstellung abhängig

- ggf. mit Kompressionsverfahren kombiniert