TECHNISCHE INFORMATIK II

Zusammenfassung zur Vorlesung von Prof. Dr. B. Plattner

Lukas Cavigelli, Juli 2011, v1.0

lukasc@ee.ethz.ch

Enthält Bilder aus Wikipedia und Textabschnitte von N. Perrenoud

EINFÜHRUNG

Aufgaben eines Betriebssystems: Mittler zwischen User (Mensch, Applikation) und Hardware Steuerung der Ausführung von Anwedungen Abstraktion der Hardware Verwaltung der Betriebsmittel Sicherheit Arten von Betriebssystemen: „monoprozess“-OS: Laufzeit-Bibliothek für einf. Anwedungen Batch-OS: maximaler Durchsatz bei Datenverarbeitung Multiprogramming: viele Prog. im Speicher, max. CPU-Last Timesharing: mehrere User, Sys. simuliert 1 Computer/User single user / multi-tasking (Windows, Linux, …) Bertriebssysteme für eingebettete und mobile Systeme Soft oder Hard Real-Time Betriebssysteme Cloud-Betriebssysteme Betriebsmittel:

Architektur eines Computersystems: Hardware (CPU, Speicher, I/O, ...) OS (hardware-management) User- & System-Applications (Editor, Compiler, Browser, ...) Aufbau eines Mainboards:

Aufbau einer CPU:

Neuerungen: Integration des Speichercontrollers auf der CPU Integration der ganzen Northbridge & GPU auf der CPU Cloud Computing: Software as a service (Verarbeitung, Speicherung, …) Pool von Ressourcen (CPUs, RAM, Disks, Kommunikation) Virtualisierung, Skalierbarkeit, Verfügbarkeit Probleme: Sicherheit, Privacy, Recht, Kühlung, ... Green Computing: Leistungs-Ansprüche steigen, Energie bisher irrelevant Ziel: linearer Zusammenhang: Energiebedarf Leistung Virtualisierung, CPU-Core-Abschaltung, ....

AUSFÜHRUNGS-MODI

Einschränkung des Befehlssatzes und Speicherbereich je nach Modus. Modi-Wechsel aufwändig (Kontext-Wechsel). Kernel-Mode: privilegiert, Funktionen für User-Programme

nur via Syscalls verfügbar. Kernel-Mode ist ein Mode-Bit (Hardware-Flag), das vom OS gesetzt wird. z.B. erforderlich für das Ein- & Ausschalten von Interrupts, ...

User-Mode: eingeschränkt, kein direkter HW-Zugriff möglich Hypervisor-Mode: Nur bei neuen CPUs. Gast-OS einer

Virtual-Machine kann im Kernel-Mode laufen ohne zu stören.

BETRIEBSSYSTEM-ARCHITEKTUREN

Monolithischer Kern (Unix, Linux): POSIX-Schnittstelle: Portable OS Interface based on UniX

Microkernel (MACH), z.B. MacOS X hat Hybrid-Kern:

Vorteile: minimaler Kern, Funktionen modular austauschbar Nachteile: Latenz bei Kommuniktion zwischen Managern

Achtung: Der Mikrokern selbst läuft allesamt im kernel-mode! Windows-Kernel

DOS und Embedded Systems: Alles im Kernel-Mode VMWare-Architektur:

Übergang User- Kernel-Mode: - periodisch erzwingbar mit Timer-Interrupt - andere Interrupts, Syscalls

Aufstarten eines Computers: Bootstrap-Programm wird beim Einschalten gestartet:

Firmware im ROM/EEPROM, initialisiert gesamte Hardware, lädt OS-Kern und führt ihn aus

Bootstrap-Prozess hat meist mehrere Stufen: BIOS Boot liest Master Boot Record (MBR) und führt Code aus MBR liest Bootstrap-Kern und führt in aus Bootstrap-Kern lädt konfigurierten Kern und führt ihn aus Konfig. Kern startet Systemprozesse und Benutzerschnittst.

EINHEITEN & GRÖSSEN

1 Byte = 8 Bits

kilobyte (kB), mega (MB), giga, tera, peta, exa, zetta ( )

kibibyte (KiB), mebi (MiB), gibi, tebi, pebi, exbi, zebi ( )

PROZESSE & THREADS

Möglichkeiten der Parallelisierung: Zeitliche Überlappung von Berechnung und I/O mit Interrupt Überlappung einezlner Schritte beim Pipelining Verwendung mehrerer Prozessoren/Cores Mehrere Programme gleichzeitig ausführen Ziele: Leistung, Preis-Leistungs-verhältnis, Komfort, verfügbarkeit, Reaktionszeit, Wartbarkeit Lösungsansatz: Mehrere Prozesse, durch FIFO-Buffer gekoppelt Weg Quellcode Prozess:

Programm : Menge von Instuktionen Prozess ( ): Programm in Ausführung, Zeit , Daten

PROZESS-VERWALTUNG

Bestandteile eines Prozesses: Stack: Aktivierungsrahmen (Stack-Frames) von

Unterprogrammen (z.B. Funktionen) Heap: Dynamischer Speicher Data: Bekannter Speicher (z.B. globale Variablen) Text: Programmcode Prozess im Speicher:

Prozesstabelle: enthält pro laufendem Prozess einen Eintrag als Linked-List. Diesen Eintrag nennt man Prozesskontrollblock. Prozesskontrollblock (PCB):

Weiterer Inhalt: Scheduling-Params, erwartetes Ereignis, Timerzustand, PID & Parent PID, User/Group-IDs Prozessumschaltung: Speichern des Prozesszustandes in den entsprechenden PCB und laden des neuen Prozesses aus dem dazugehörigen PCB.

Prozess-Erstellung: fork() Prozess gabelt sich auf in zwei Kontrollflüsse mit gleichem

Code. bei Unix ist der init-Prozess der erste Prozess (PID 1). Waise (orphan): Kindprozess ohne Elternprozess, ParentPID 1 Zombie: terminierter Kindprozess, der vorerst weiterexistiert

PROZESS-SCHEDULING

Langzeit-Scheduling (Job-Scheduling): Verwaltet welche Prozesse im Speicher und welche ausgelagert sind. Nur aktiv, wenn Prozess terminiert oder zuwenig Speicher. Kurzzeit-Scheduling (CPU-Scheduling): Wird aufgerufen, wenn nächster Prozess an der Reihe ist (wählt aus der Ready-Queue). Ziel: max. Durchsatz, CPU-Auslastung, Fairness. Lebenszyklus/Prozesszustände:

KURZZEIT-SCHEDULING

Zeitbegriffe: Ausführungszeit (Turnaround-Time TT): Mittlere Zeit,

zwischen Erstellen und Abschluss eines Prozesses. Enthält alle Zeiten in Warteschlangen, Bedienzeit, I/O-Zeit. ∑

Bedienzeit: Zeit, welche der Prozess effektiv benötigt Mittlere Antwortzeit (Response Time RT): Mittlere Zeit bis

neuer Prozess erstes Mal CPU erhält. ∑

I/O-bound v. CPU-bound: Ein Scheduler sollte Prozesse in I/O-bound und CPU-bound klassifizieren. I/O-Prozesse belasten CPU kaum, CPU-bound Prozesse benötigen jedoch meistens den ganzen time-slice. Aktivierungsgründe: 1. Prozess wird blockiert durch I/O-Operation, Syscall, ... 2. Laufender Prozess wird bereit (Interrupt, z.B. Timer) 3. Blockierter Prozess wird bereit (I/O fertig Interrupt) 4. Prozess terminiert (Syscall) 5. Laufender Prozess wird freiwillig bereit (Syscall) Scheduling-Arten: Non-preemptive: Prozess läuft bis er freiwillig CPU abgibt

Nur Gründe 1, 4 & 5 können auftreten. Preemptive: Prozess läuft nur solange er darf. Keine

Blockierung durch einzelnen Prozess möglich. Priorisierung möglich. Aufwändiger. Alle Gründe können auftreten.

Scheduling-Algorithmen: FCFS: first come, first served. non-preemptive. SJF: shortest job first. Prozess mit kürzester CPU-Belegung

zuerst. preemptive oder non-peremptive möglich. PS: priority scheduling. Prozesse mit höherer Priorität vor

anderen. Wenn mehrere dieselbe Priorität haben: round-robin. Problem: Starvation von Prozessen niedriger Priorität. Lösung: Aging – Priorität steigt mit Zeit in Warteschlange

RR: round robin. FCFS mit time-slicing im Intervall . Regelmässige Neuzuteilung der CPU und Prozessen in der Warteschlange. Nach Ausführung hinten wieder anfügen. preemptive oder non-preemptive möglich.

MLS: multi-level-scheduling. Prozesse werden statisch in Klassen eingeteilt, die separat behandelt werden. premptive oder non-preemptive

MLFQ: multi-level-feedback-queue. Wie MLS, aber dynamisch RTS: real-time-scheduling. Ereignisse müssen innerhalb einer

First behandelt werden. preemptive oder non-preemptive. LRU: least-recently-used. CFS: completely fair scheduler, ab Linux Kernel 2.6.23

SYNCHRONISATION

Kritischer Bereich: Abschnitt eines Prozesses oder Threads, in welchem auf eine gemeinsame Ressource zugegriffen wird. Race Condition: Wenn Resultat eines Abschnitts vom zeitlichen Verhalten bestimmter Einzeloperationen abhängt. Anforderung an Behandlung kritischer Bereiche: mutual exclusion: zwei Prozesse dürfen nie gleichzeit in

kritischem Bereich für dieselbe Resource sein. Jeder Prozess muss irgendwann den krit. Bereich betreten

dürfen. Ewiges Warten darf nicht möglich sein (fairness). Prozesse ausserhalb eines krit. Bereiches dürfen einander

nicht blockieren. Es dürfen keine Annahmen über Abarbeitungsgeschw. oder

Anzahl Prozesse getroffen werden. Synchronisationsmethoden: Semaphoren (siehe unten) Locks & Conditions: Wie Semaphoren, haben aber einen

Besitzer. Nur dieser kann die Sperre freigeben. Latch: Gemeinsamer Synchronisationspunkt Barrier: Mehrfach verwendbares Latch Rendez-vous: Latch mit Interaktion, z.B. Datenaustausch Probleme bei der Synchronisation: Verklemmung (Deadlock): Mehrere Prozesse schliessen sich

gegenseitig aus und warten für immer. Tritt auf, wenn alle: o Mutual Exclusion: Jede Resource nur einfach belegbar o Hold and Wait: Prozesse, die die Ressource belegt haben,

warten auf weitere Resource. o No preemption: OS kann Resource nicht wegnehmen o Zyklische Wartebedingung: zykl. Kette von Prozessen, die

alle auf dieselbe Resource warten. Diese ist aber bereits durch Nachfolger in der Kette belegt. Bsp.: Dining Philosophers. Lösung: Ein Prozess nutzt andere Richtung

Verhungern (Starvation): Ein Prozess kommt durch ungünstiges Scheduling nie an die Reihe.

SEMAPHOREN

Typen von Semaphoren: Binary Semaphore (mutex): oder . Gegenseit. Ausschluss Counting Semaphore: bis . Zum Zählen einer Anzahl Elem. Funktionen von Semahoren: Dekrementieren: dec, down, acquire, wait, lock, P Inkrementieren: inc, up, release, signal, unlock, V, post

Beispiel: Barriere s = new semaphore(1);

function thread1() {

s.wait(); /*critical section */

s.signal(); }

Beispiel: Rendez-vous s1 = new semaphore(0);s2 = new semaphore(0);

function thread1() {

//before rendez-vous

s2. signal(); s1.wait(); }

function thread2() {

s1.signal(); s2.wait(); }

Beispiel: Resource mit 3 freien Einheiten s = new semaphore(3);

function thread1() {

s.wait(); /* do something with resource */

s.signal(); }

INTERPROZESS-KOMMUNIKATION ( IPC)

Charakteristiken: Direkte oder indirekte Kommunikation, Speicherfähigkeit des Kanals, bekannte Anz. Endpunkte. Nichrichtenstruktur nicht vorgegeben. Konzepte: Shared Memory: (indirekt): Alle dürfen gleichzeitig zugreifen Message Queue/Passing (indirekt): Reihenfolge der

Nachrichten gegeben. Jeder, der Ablage kennt, kann etw. abl. Pipes (direkt): Direkte Verbindung Sender-Empfänger.

Reihenfolge gegeben. OS-Signale (direkt): Mehrere Signale gleichzeitig möglich.

Reihenfolge daher nicht gegeben.

THREADS

Verschiedene Threads: User Space Thread: Jeder Prozess hat eigene Threadtable und

Scheduler für Threadverwalt. Kernel wählt nur Prozess aus. Kernel Space Thread: Kernel hat & verwaltet auch Threadtbl. Unterschied Prozess Thread: Prozess: Instanz eines Programms Thread: Sequentieller Abarbeitungslauf eines Programms

Threads teilen sich die Betriebsmittel (Speicher, Dateien, ...) des Prozesses. Jeder Thread hat eigenen PC, Stack, Register und Zustandsinfo.

nur Prozess: Adressraum, globale Variablen, File-Handles, Kindprozesse, Signale & -handler, Accounting Information

wird Prozess durch I/O geblockt, werden auch alle Threads geblockt!

SPEICHERVERWALTUNG

Voraussetzungen für Speichermanagement: HW: Speicherschutz, OS: muss entsprechenden Code enthalten Merkmale von Speichersystemen: Geschwindigkeit, Grösse, Kosten, Flühtigkeit Begriffe: MMU (Memory Management Unit): Ermöglich Zugriff auf

gesamten virtuellen Adressraum, kapselt Prozesse voneinander ab. Verhindert Speicher-Fehlzugriffe.

TLB (Translation Lookaside Buffer): Einheit der MMU. Rechnet virtuelle in physische Adressen um. Kann begrenzte Menge an Übersetzungen cachen (64-128 Einträge). Beschleunigt dadurch den Speicherzugriff.

Demand-Paging: Teilbereiche des durch einen aktiven Prozess genutzten Speichers werden wiederverwertet.

Monoprogrammierung: 1 Prozess im Speicher Statische Speicherverwaltung: Prozesse werden nur einmal

in den Speicher geladen (vs. dyn. Speicherverwaltung) Monolithisch: Prozess als Einheit verwalten (vs.

Segmentation, Paging) Mechanismen zur Speicherverwaltung: linear: statisches Speicherbild (alles bleibt immer gleich) swapping: Ein- und Auslagern ganzer Prozesse in/aus dem

Hauptspeicher zur Laufzeit (bei dyn. Speicherverwaltung). Benötigt viel Zeit, weil Prozesse als Einheit behandelt werden

relocation: Dynamisches Binden von Adressen mittels Offset. Bei Multiprogramming (mehrere Prozesse im Speicher) erforderlich zur Anpassung des Speicherbildes an aktuelle Situation. Benötigt MMU (memory management unit).

paging (seitenverwaltung): Dynamisches Ein- und Auslagern von Speicherblöcken konstanter Grösse (Seiten, pages). Nicht jede logische Adresse hat jederzeit auch eine physische. dann entsteht eine page-fault/page-miss und das OS lödt die Daten in den Speicher. Unterkapitel Paging

virtual memory: dynamisches Binden von Speicheradressen zur Laufzeit

segmentation: dynamisches Ein- und Auslagern von logisch zusammengehörigen Bereich (z.B. Array) Unterkap. segm.

Verhalten bei vollem Swap-Speicher: Prozess beenden Andere Prozesse aus Swap wiedereinlagern Schlafenlegen anderer Prozesse ohne Auslagerung Virtueller Adressraum: Stellt für jeden Prozes den gesamten Adressraum bereit. Physisch wird der Speicher eines Prozesses dadurch verschiebbar. CPU generiert virtuelle/logische Adressen, MMU übersetzt diese zu physischen. Adressarten: todo Aufteilung des virtuellen Speichers: Kernel-Space: Reserviert für Kernel, -erweiterungen &

Treiber. Wird meist nie ausgelagert. Threads im Kernel-Space werden vom CPU-Scheduler verwaltet.

User-Space: Hier laufen alle User-Mode Programme. Kann ausgelagert werden. Threads werden durch App. verwaltet.

ADRESS-BINDUNG

Bindung zur Compile-Zeit: Adoslute Adressierung, keine

Relokation Bindung zur Load-Zeit: Relokation nur bei Neuladen möglich Bindung zur Laufzeit: Relokation während Ausführung

möglich. Physikalischer und logischer Adressraum.

SPEICHERZUTEILUNG

Buchführung: Zuordnung durch feste Tabelle (Tabelleneinheit gibt Zustand

an; belegt oder unbelegt) Zuordnung durch linked-list: start, länge speicherber., next Algorithmen für Speicherzuteilung: First-Fit: erster passender Bereich wird verwendet Next-Fit: First-Fit, aber Allokationspointer wird mitgeführt Best-Fit: Der best-passende wird verwendet Worst-Fit: Grösster verfügbarer Bereich wird verwendet Quick-Fit: Eine Liste pro gebräuchlicher Anforderungsgrösse,

z.b. pro Datentyp, wird geführt.

Buddy: Speicherbereiche ausschliesslich mit Längen . Bewertung: Belegungsgrad,Zeitaufwand Allokation,Komplexität Vergleich: First-Fit oft besser als Next-Fit, Best-Fit und Worst-Fit

Quick-Fit gut, wenn entspr. Kenntnisse vorhanden. Buddy-Systeme: ca. 75% des Speichers kann genutzt werden. Speicherfragmentierung: Externe Fragmentierung: Nicht zugeteilte Speicherbereiche

können nicht genutzt werden, da nicht genügend zusammenhängender Speicher verfügbar.

Interne Fragmentierung: Nicht genutzter Speicherplatz innerhalb von zugeteilten Bereichen.

Garbage Collection: Periodisches Verdichten des Speichers bei Bedarf. Teuer oder unmögl. bei statischer Adressierung

Defragmentierung: Verschieben von Prozessen im Speicher. Vermindert externe Fragmentierung. Führt zu geänderter Speicherzuteil. Stack-Pointer, ... müssen angepasst werden

PAGING

Page Frames: Physischer Speicher wird in Seitenrahmen (page frames) fester Länge aufgeteilt (2er-Potenz zw. 512 - 8 KiB) Pages: Virtueller Speicher wird in Pages gleicher Länge geteilt Übersetzung: Erfolgt mittels Seitentabelle. Jeder Prozess hat davon seine eigene. Das PTBR (page table base register) enthält die Adresses der Seitentabelle des aktiven Prozesses. Die page table selbst ist meist im Speicher oder gar der Harddisk abgelegt. Seitentabelle werden durch das OS geladen. Paging löst das Problem der externen Fragmentierung, jedoch nicht dass der internen. Wird schneller durch TLB. Relokation: Nur page table des Prozesses nachzuführen.

Speicherschutz: Jeder TLB-Eintrag enthält ein Validity-Bit. Dadurch können Fehlzugriffe abgefangen werden. Logische Seitenadresse: Besteht aus zwei Teilen: Adresse des Seitenframes (IA32: 20 Bit 1‘048‘576 pages) Offset: Position innerhalb des Frames (12 Bit 4096) Struktur eines Seiteneintrages (page frame):

Seitenfehler: Bei jedem Verfahren kann eine virtuelle Adresse auf eine nicht im Speicher befindliche Seite zeigen. Diese Muss dann erst durch Paging in den Speicher geladen werden (demand paging). Wenn die MMU im Statusbit der entsprechenden page einen „nicht geladen“ –Eintrag vorfindet, meldet sie dies ans OS durch einen Seitenfehler. Demand Paging: Ein Seitenfehler führt zu einer Exception (Trap), wodurch die Seite geladen und die page table aktualisiert wird. Diese Technik bezeichnet man als Demand Paging (Seite wird erst geladen, wenn sie gebraucht wird). Effective Access Time (EAT):

EAT = (1 “page fault rate”) “memory access time” “page fault rate” ”average page fault service time”

Copy-on-Write: Prozesse verwenden nach fork() dieselben Seiten. Erst wenn ein Prozess eine Seite modifiziert, wird diese dupliziert. Trashing: Ab einem gewissen Parallelitätsgrad kommt es zum Trashing. Das bedeutet eine hohe CPU-Last wegen vielen Seitenfehlern tiefe Nutzleistung Kriterien zur Seitenersetzung: Zugehörigkeit der Speicherseite zum aktiven Prozess

Es hat sich gezeigt, dass Prozess-Scheduling-Algorithmen, welche die Speicherseiten nicht nach Prozess aufteilen, effizienter sind. Insbesondere wenn bei laufendem Betrieb die Grösse des Hauptspeichers geändert wird.

Letzter Zugriff auf die Speicherseite R-Bit (Reference-Bit) zeigt, ob auf die Speicherseite zugegriffen worden ist. Je nach Implementierung Zeitstempel oder periodischer Reset aller R-Bits auf 0.

Unversehrtheit der Speicherseite M-Bit (Modification-Bit) zeigt an, ob sich der Speicherinhalt gegenüber dem auf der Festplatte geändert hat. Wird die Seite ausgelagert, muss man sie nur mit M-Bit 1 zurückschr.

AUFBAU VON PAGE TABLES

Einstufige Seitentabelle: Adressumsetzung: höherwertige Bits eine virtuelle Adresse = Seitennummer niederwertige Bits = Offset Seitennummer bestimmt ausgehend von der Basisadresse der Seitentabelle (im PTBR) den Eintrag in der page table, aus dem die Basisadresse der realen Speicheradresse gelesen wird.

Weiters beinhaltet die page table Statusinformationen über die page, die z.B. Auskunft geben, ob die Seite im RAM ist, oder ob sie seit dem letzten Zugriff verändert wurde.

reale Adresse = (Basisadresse der page << ) | (offset)

Hashtabelle: Verzeichnet nur tatsächlich verwendete Seiten. Seitennummer der virt. Adressraums wird als Key verwendet Invertierte Seitentabelle: Pro Page-Frame ein Eintrag mit der Information über die zugehörigen Seiten. Eintrag enthält Seitennummer und ID des Prozesses, dem die Seite gehört. Benötigt Zeit für Suche, vermindert Speicherplatz. Probleme bei gemeinsamer Nutzung von Frames durch mehrere Prozesse. Hierarchische Seitentabelle (2-, 3-, 4-Level): Tabelle wird in Teile mit der Länge einer Seite aufgeteilt. Die äussere Tabelle hat einen Eintrag für jede Seite der inneren Tabelle. Jede Seite der inneren Tabelle hat einen Eintrag pro Seite. Adressumsetzung ( -stufige page table): Bits der virt. Adresse = Seitentabellenverweise niederwertige Bits = Offset blaabla blaabla blaabla blaabla blaabla blaabla blaabla

Adresse in der page table 1ter Stufe ist gleich lang wie reale Adr

Beispiel: 3-stufige page table Gegeben: 2-stufie page table, Verhältnis 1:2:4, d.h. zweite doppelt so gross wie die erste, dritte wiederum doppelt. 32bit System, Wortadressier. (4 Byte kl. Einheit), Offset 14 bit page size: mögl. pages, Grösse: KiB Bits für Index in der page table: . Also: . Also hat Tabelle 1 Einträge,

Tabelle 2 hat Einträge, Tabelle 3 deren

Speicherverbrauch der dritten page table: Byte, da jeder Eintrag 4 Byte benötigt gesamter Speicherverbrauch der page tables summieren

Beispiel: Offset-Berechnung Gegeben: 32bit-System, page size 4 KiB, Wortadressierung

4096 Byte / 4 Byte = 1024 Wörter = Einträge. Der Offset ist also 10 Bits. Es bleiben 22 bit für die page table

SEITENERSETZUNGSSTRA TEGIEN

Für jede Seite wird ermittelt, vieviele Instruktionen ausgeführt werden, bis auf die Seite zugegriffen wird. Es wird die Seite mit der grössten Anzahl gewählt. FIFO: first in, first out. Älteste Seite wird ersetzt. Es wird der

Zeitpunkt des letzten Eintritts in den Hauptspeicher betrachtet. Wird selten verwendet wegen Belady-Anomalie.

SC: second chance. Weiterentwicklung von FIFO. Zusätzl. wird geprüft, ob Seite referenziert wurde (R-Bit). Falls ja: R-Bit löschen und an Anfang der Schlange setzen.

Clock Replacement: Schnellere Implementierung von SC. Kein Vertauschen, sondern Zeiger auf älteste Seite.

LRU: least recently used. LFU: least frequently used. Zugriffszähler pro Seite. Seite mit

wenigsten Zugriffen wird entfernt. MFU: most frequently used. Wie LFU, aber umgekehrt. NRU: not recently used. Seiten, die innerhalb eines

Zeitintervalls nicht benutzt und nicht modifiziert wurden, werden bevorzugt ausgelagert. Danach werden Seiten, die nicht benutzt oder nicht modifiziert wurden und zuletzt erst Seiten, die benutzt und modifiziert wurden.

NFU: not frequently used. Seitenzugriffe werden mit zeitlichem Abstand zur aktuellen Anfrage korreliert und so ein Wert ermittelt. NFU ist Variante von LRU in Software.

CLIMB: Wird eine Seite, die sich im Speicher befindet referenziert, steigt diese auf. Ersetzt wird immer tiefste Seite.

SEGMENTATION

Adressbindung: Abbildung von virtuellen auf physische Adressen bei segmentiertem Speicher: 1. Ein Anteil der virtuellen Adresse wird als Segment Pointer in

die Segmenttabelle verwendet. 2. Der Eintrag, auf den der Segment Pointer zeigt enthält die

physische Basisadresse und Grösse des Segments. 3. Summe der Basisadresse und des Offsets bilden echte Adr. weitere Beispiele aus MC-Aufgabem!!

INPUT & OUTPUT

Zugriffsmechanismen: Interrupts: Unterbrechung der CPU, ausgelöst durch Gerät Polling: Ermitteln des Zustandes eines Geräts durch

periodische Abfragen. Aktives Warten (busy waiting). Programmed I/O: Kopieren von Daten durch CPU. Grosse

CPU-Belastung. DMA (Direct Memory Access): Kopieren von Daten urch

spezielle Hardware (DMA-Controller). Kopieren von Daten zwischen I/O-Geräten und Speicher keine CPU-Belastung

I/O-Art: blockierend: blockiert bis ein Ergebnis vorliegt. nicht blockierend: blockt nicht, liefert sofort Statusmeldung Sender/Empfänger: Synchron: Sender muss warten bis er eine Bestätigung des

Datenempfangs erhalten kann. Asynchron: Benötigt Puffer. Senden und Empfangen unabh. IRQ-Tabelle:

IRQ Verwendung IRQ Verwendung

0 System-Taktgeber 8 Echtzeituhr (RTC) 1 Tastatur 9 Zu IRQ 2 umgeleitet* 2 Kaskadiert ZU IRQ 9 10 frei, ggf. PCI-Bus 3 COM 2, 4, 6, 8 11 frei, ggf. SCSI 4 COM 1, 3, 5, ,7 12 PS/2 5 frei, ggf. LPT 2 13 Mathm. Coproz. FPU 6 Floppy Disk 14 Primary IDE 7 LPT 1 15 Secondary IDE

*) aber auch VGA und NIC, IRQ 16-23 Performance-Konzepte: Caching: Schneller Speicher hält Kopie von Daten Spooling: Zwischenspeichern von Ausgabedaten für externe

Geräte (wenn diese Aufträge sequentiell abarbeiten) Reservation: Syscall zur de-/allokation des Gerätes

GERÄTEMODELLE & SCHNITTSTELLEN

Zugriffsarten: Wahlfreier Zugriff (random access): RAM, HDD, DVD, CD Sequentieller Zugriff (sequential access): Terminals,

Bandlaufwerke, A/D-Wandler Orientierung: Blockorientierte Geräte (block devices): HDD, CD, DVD.

Befehle: read, write, seek. Zugriff via Dateisystem. Memory mapped I/O möglich.

Zeichenorientierte Geräte (char devices): Tastatur, Maus, USB, Sound, Drucker. Befehle: get, put

Spezielle, weitere Geräte: Netzwerke-Geräte: Befehle: select, poll. Arbeit mit Sockets. Virtuelle Geräte: /dev/null und /dev/urandom

FESTPLATTEN

Geometrie:

Probleme der Magnetisierung: Konstante Magnetisierungsdichte, unterschiedl. Spurlängen konstante Sektorenzahl durch gesteuert abnehmende Schreibdichte

Ineffektives Ausnutzen der Speicherdichte Einteilung der Platte in 20-40 Zonen

Moderne Massenspeicherarten: Network Attached Storage (NAS): Zugriff via Netzwerk (NFS,

SMB, CIFS, AFS, ...). Storage Area Network (SAN): Viele Rechner verbunden,

liefern riesen Speicher (GoogleFS, CosmosFS). Redundant Array of Inexpensive Disks (RAID): Mehrere

Platten liefern im RAID grösseren oder redundanten Speicher. Scheduling: Ziel: Optimierung der Suchzeit und der Durchsatzes Zugriffszeit besteht aus Seek-Time (Suchzeit, Lesekopf über Spur positionieren) und Rotational Delay (bis Platte zu entsprechendem Sektor gedreht hat) Zugriffszeiten: Mittlere Suchzeit pro Spur:

Mittlere Rotationsverzögerung

, : Umdrehungszeit

Mittlere Zugriffszeit: Transferzeit für Bytes bei einer Spurgrösse (nicht

Sektorgrösse) von Bytes: .

Relativer Spuranteil:

, Datentransferrate:

Gesamtzeit:

Zugriffsarten: FCFS: first come, first served. Sucht Blöcke nach zeitlicher

Reihenfolge der Anfragen. SSTF: shortest seek time first. Wählt Block mit kürzester

Suchzeit. Starvation möglich! SCAN: Elevator Algorithm. Lesekopf bewegt sich vom einen

zum anderen Ende der Platte und zurück. C-SCAN: Wie SCAN, aber statt Umkehren zurückspringen

gleichmässigere Wartezeit. C-LOOK: Wie C-SCAN. Lesekopf geht aber nur soweit raus, wie

Anfragen vorhanden sind, springt dass zu innerster Anfrage. SSTF und C-LOOK oft verwendet. SCAN und C-SCAN für Systeme mit grossen Lasten

Beispiel: Berechnung der Zugriffszeiten 500 GB HDD, 7200 RPM. Mittlere Zeit um Lesekopf über beliebiger Spur zu platzieren: 9.2 ms. Sektorgrösse 512 Bytes und eine Spur besteht aus 1024 Sektoren. Durchschnittliche Zeit um Sektor zu lesen:

Wie lange dauert es mindestens um Sektorzu lesen?

RAID:

Level Erklärung Bild

RAID 0

#HDDs: Fehler-Toleranz: Platz-Effizienz: Lese- Geschw.: -fach Schreib-Geschw.: -fach Block-level striping without parity or mirroring

RAID 1

#HDDs: Fehler-Toleranz: HDDs Platz-Effizienz: ⁄ Lese- Geschw.: -fach Schreib-Geschw.: -fach Mirroring without parity or striping

RAID 2

#HDDs: Fehler-Toleranz: HDD

Platz-Effizienz:

( )

Lese- Geschw.: variabel Schreib-Geschw.: variabel Bit-level striping with dedicated Hamming-code parity.

RAID 3

#HDDs: Fehler-Toleranz: HDD Platz-Effizienz: ⁄ Lese- Geschw.: -fach Schreib-Geschw.: -fach Byte-level striping with dedicated parity.

RAID 4

#HDDs: Fehler-Toleranz: HDD Platz-Effizienz: ⁄ Lese-Geschw.: -fach Schreib-Geschw.: -fach Block-level striping with dedicated parity.

RAID 5

#HDDs: Fehler-Toleranz: HDD Platz-Effizienz: ⁄ Lese- Geschw.: -fach Schreib-Geschw.: -fach Block-level striping with distributed parity.

RAID 6

#HDDs: Fehler-Toleranz: HDDs Platz-Effizienz: ⁄ Lese- Geschw.: -fach Schreib-Geschw.: -fach Block-level striping with double distributed parity.

DATEISYSTEME

Namensraumtypen: Hierarchische Namensraum: Verzeichnisbaum mit Ordner als

Knoten, gleiche Dateinamen möglich (untersch. Verzeichnis) Flacher Namensraum: Alle Dateien auf einer Ebene

LINKS

Hardlinks: können über mehrere Hierarchien verlinken Original nicht von Link unterscheidbar nicht über Partitionsgrenzen möglich Hardlink-Counter im Inode wird für das Löschen einer Datei

benötigt (löschen erst löschen wenn alle hardlink gelöscht) Softlinks ( = symbolic link): Selbst ein File. Verweis auf Pfad der Datei/des Verzeichnis

(bei neueren Implementierungen nur eine Inode ohne Block) relative Pfadangaben möglich Links bleiben nach Löschen der Originaldatei vorhanden Pfad wird direkt im Directory gespeichert über Partitionsgrenzen hinweg möglich Ziel muss nicht existieren Link nicht im Inode des Ziels vermerkt

DATEIEIGENSCHAFTEN

Dateiattribute: Name, Typ, Dateilänge, timestamp (erzeugung, änderung,...), Addtribute (hidden, system, archive), Ort, Inode Nummer Sicherheitsattribute: Erzeuger, Besitzer, Benutzer, entsprechende Rechte

1 Entry-Type: first letter of first column d: directory, b: block special file, c: character special file, l: symbolic link, p: FIFO, s: socket, -: regular file 2,3,4 Permssions: three triplets (rwx) for each permission grp Permission groups: 2: u: owner, 3: g: group, 4: o: other (alle) Access rights: (file / directory) r ( 4): read file / view directory contents (read file list) w (2): write file / create and delete files in directory x (1): execute file / search files in directory o the x will be an s, if setuid and setgid is also set

setgid/setuid: set user id, set group id upon execution.Das Programm wird mit den Rechten der Gruppe / des owners ausgeführt sticky-bit bei files: Programm nach Beenden im RAM belassen. sticky-bit bei directories: Files in diesem directory (das z.B. rwx für alle hat) können nur vom owner gelöscht/renamed werden. 5 Number of Links: 2te Spalte zeigt die Anzahl Links auf das file. 6,7 Owner/Group: 3te & 4te Spalte zeigen user bzw. group 8 Filesize: 6te Spalte, Dateigrösse in Bytes 9 Timestamp: 5te Spalte atime (ls –u) access time: updated on read access file close mtime (ls) modify time: updated on write access file close ctime (ls –c) creation/change time: updated on inode

modification (change of ownership, size, permission, …) 10 File name: 7te Spalte, Dateiname

INODE / FILE C ONTROL BLOCK

File Descriptors: Nummer der offenen Datei, FDs sind pro Programm fd = 0: stdin, fd = 1: stdout, fd = 2: stderr Zugriff auf offene Dokumente:

Eine Datei kann mehrfach geöffnet werden. Mehrere File Descriptoren Systemweite open-file table enthält pro Eintrag einen FCB Inode EXT2: Zentrale Tabelle pro Datei: Inode (Index-Knoten) Verwaltungsdaten (Referenzen, mount()-Tabelle, Zeiger für

free-list), Adressen von Datenblöcken, Zeiger auf weitere Verzeichnis = File = Tabelle mit Einträgen (Namen + Inode-Nr) mit Annahme Blockgrösse 1 KiB, 32-bit Adressen:

[durch bild aus vorbesprechung serie 5 ersetzen] Max. Anz.Einträge in block table wird beim erstellen des FS def. Genau 1 file pro Block u.U. grosse Verluste bei kl. Dateien. [Bild Partitionsstruktur ext2 (vorbespr.)]

IMPLEMENTIERUNG DES DATEISYSTEMS

DATEIEN

Grundprinzipien: Speicherplatzaufteilung in Blöcke Verwaltung frei/belegt Struktur von Files Zusammengehörigkeit von Blöcken Struktur von Directories: Zentrale Speicherung der Dirs,

Verzeichnisse als spezielle Files Format der Einträge Struktur von Disks & Paritionen Dateiimplementierung: zusammenhängend: schnell, schwer modifizierbar linked-list von Blöcken:

- random access ineffizienz, nur sequentiell möglich + Rekonstruktion möglich bei Anker-Löschung

double-linked-list: auch „zurückspulen“ möglich Dateityp-Erkennung: Dateinamenendung (.docx, ...) (windows) Es gibt noch eine Möglichkeit „magic number“: erkennen an ersten paar Bytes der Daten

zentraler Index: zentrale indexbezogene Speicherzuweisung, zentraler Block von Zeigern in einer Liste:

sssssssssssss

VERZEICHNISSE & PART ITIONEN

Bootsektor einer FAT-formatierten Diskette: Sektorgrösse, Clustergrösse, Anz. FAT Kopien, Anz. Sektoren, Anz. Sektoren/Spur, max. Anz. Verz. pro Wurzelverzeichnis, ...

FATx: balbla

FAT-DATEISYSTEM

balbla

VIRTUAL FILE SYSTEM (VFS)

Ermöglicht gleichzeitige Verwendung mehrerer verschiedener Dateisysteme.

Prinzip: Einhängen eines anderen dateisystems durch mounten auf einen mount-point (= Verzeichnis), überdeckt ursprünglichen Verzeichnisinhalt.

Problem: Inode-Nummern, welche jeweils für ein einzelnes Dateisystem eindeutig sind, verlieren ihre Eindeutigkeit. Hardlinks in ein anderes Dateisys. funktionieren nicht richtig

Lösung: Das VFS definiert eine neue ID. Deshalb werden die Hardlinks auf Dateien im eigenen Dateisystem eingeschränkt (da diese auf Inode-Nummern zeigen).

JOURNALING

Jeder Schreibvorgang wird VOR dem eigentlichen Schreibvorgang in einem Journal dokumentiert, um nach einem Absturz die Dateisystemkonsistenz schnell überprüfen zu können. Es könnte z.B. zu einem Absturz während eines Löschvorgangs kommen, die wie folgt abläuft: Directory-Eintrag löschen, Datenblöcke in die Liste der freien Blöcke aufnehmen, Inode löschen. (Absturz nach erstem Schritt: Datenblöcke und Inode werden zu „Leichen“).

COMPUTERNETZWERKE

Begriffe: Server: Anbieter von Dienstleistungen, Besitzer der

„gesamten Intelligenz“ und deshalb einfache zentrale Verwaltung

Client: Benutzer der Deinste eines Servers DNS (Domain Name System): Übersetzt Namen in Adressen

mit Hilfe eines hierarchischen Namensschemas (.ch ethz ee people IP)

Peer-to-Peer: Jeder Computer ist mit jedem anderen verbunden und alle sind gleichberechtigt, können Dienste anbieten oder in Anspruch nehmen. Ausfallsicher.

Netzwerkarten: o Punkt-zu-Punkt: Ein Link verbindet zwei aktive

Komponenten o Mehrfachzugriff: Ein Link verbindet mehrere aktive

Komponenten untereinander Verbindungsloser Dienst:

z.B. IP, keine DIREKTE Verbindung nötig Verbindungsorientierter Dienst:

z.B. Telefonie, über direkte Verbindung Multiplexingverfahren: Ziel: Gemeinsame Verbindungen auf einem Link: Frequenzmultiplexing: Unterteilung in kleine Frequenzräume Zeitmultiplexing: Mehrere Zeitscheiben (Handy) Raummultiplex: Verbindungen in unterschiedlichen Regionen Codemultiplex: Codes zur Unterscheidung der versch. Verb. Vermittlungstechniken: Leitungsvermittlung: Die Daten werden von zwei Endknoten

über eine direkte Verbindung ausgetauscht Paketvermittlung: Die Daten werden von allen Endknoten

gemeinsam übermittelt und bei jedem Zwischenknoten wird eine Entscheidung über die Weiterleitung getroffen.

LEITUNGSCODIERUNG

Binäre Leitungscodes: Im einfachsten Fall wird den logischen Zuständen 0 und 1 ein Pegel auf der physikalischen Leitung zugeordnet. Beim seriellen RS-232-Protokoll entspricht z.B. eine neg. Spannung einer logischen 1, eine pos. Spannung einer logischen 0. Werden jetzt lauter 1 übertragen, tut sich auf der Leitung nicht. Dadurch können bei asynchronem Takt nur wenige (5 bis 8) Bits in einem Block übertragen werden, die mit einer Startsequenz

gekennzeichnet werden, oder es ist eine zusätzliche Taktleitung zur Synchronisation nötig. Serielle Übertragung (RS-232):

Manchesterkodierung: Dies wird durch die Manchesterkodierung geändert: Hie entspricht eine 0-1-Folge einer logischen 0 (steigende Flanke), eine 1-0-Folge (fallende Flanke) einer logischen 1. Manchestercode:

Hierdurch wird erreicht, dass: 1. stets Pegelwechsel zur Taktrückgewinnung vorhanden 2. Gleichspannungsanteil im Mittel gleich null Es verdoppelt sich allerdings die erforderliche Datenrate (die Schrittgeschwindigkeit wird halbiert). Die Leitungscodes sollten bei elektrischer Übertragung im Mittel gleichspannungsfrei sein, weil eine Übertragung von Gleichspannung über lange Leitungen nicht möglich ist. Ausserdem sind im Übertragungspfad häufig Transformatoren als Potentialtrenner eingefügt. Bei längeren Übertragungsstrecken werden zudem Regenerationsverstärker bzw. Repeater eingefügt. Ist das Nachrichtensignal gleichspannungsfrei, so können über dasselbe Koaxkabel diese Verstärker mit Gleichstrom ferngespeist werden. Der Manchestercodeleistet die Gleichspannungsbeseitigung automatisch, da sowohl 01 als auch 10 gleichspannungsfrei sind Differentieller Manchestercode: Beim differentiellen Manchestercode steht ein Polaritätswechsel am Taktanfang für eine logische 0 (zwei Flankenwechsel pro Bit), bei einer logischen 1 erfolgt kein Polaritätswechsel am Taktanfang (1 Flankenwechsel/Bit).

HDLC (HIGH LEVEL DAT A LINK CONTROL)

Zeichenorientiertere Rahmenbildung für Bitfolgen. DLE: Data Link Escape. Nach diesem Zeichen folgt ein

Steuerzeichen. Falls in normalem Text ein DLE-STX o.ä. vorkommt, wird ein zweites DLE vornedran gestellt, um die Sequenz zu „escapen“ (character stuffing)

STX: Start of Text ETX: End of Text Bei HDLC bestehen die Rahmen z.B. aus 0111 1110 Beispiel: Ein Sniffer hat den folgenden HDLC encodierten Bitstrom aufgefangen. 01111110 10101111 11001111 11000000 01111101 01111110 Rekonstruieren Sie die übertragenen Daten. 101000000111111 Mit welchem Verfahren werden in HDLC Datengrenzen übermittelt. Framing (Rahmenbildung) Mittels welchem Verfahren kann eine Verwechslung von Datengrenzen und Daten ausgeschlossen werden. Bit Stuffing (zB. eine 0 einfügen, wenn eine 1 den rahmen vervollständigen würde)

Sicherungsprotokoll-Übersicht:

Sende- puffer

Empfangs-puffer

Folge-nummer

Timer

IRQ mit NAK Ja

Selective CRQ Ja

Go-Back CRQ Ja

BILD OSI-LAYER MODELL

NETZWERKPROTOKOLLE

Netzzugangsschicht 1 & 2: Ethernet CSMA/CD: Netzwerkstandard IEEE 802.3 WLAN: Netzwerkstandard IEEE 802.11 PPP: Point-to-Point Protokoll RFC 1661 PPPoE: Point-to-Point over Ethernet Token Bus: Netzwerkstandard IEEE 802.4 Token Ring: Netzwerkstandard IEEE 802.5 FDDI: Fiber Distributed Data Interface Vermittlungsschicht (Internetschicht) 3: IP: Internet Protokoll. Datenpaket-Übertragung

(verbindungslos) ICMP: Internet Control Message Protokoll.

Kontrollnachrichten (z.B. fehlermeldungen), Teil jeder IP-Implementierung

IGMP: Internet Group Management Protocol. Dient zur Organisation von Multicast-Gruppen. Integraler Bestandteil von IP auf allen Hosts, die den Empfang von IP-Multicast unterstützen.

OSPF: Open Shortest Path First. Informationsaustausch zwischen Routern (Linkzustand) via IP.

BGP: Border Gateway Protocol. Informationsaustausch zwischen autonomen Systemen im Internet (Pfadvektor) via TCP

ARP: Address Resolution Protocol. Adressumsetzung zwischen IP- und Geräte-Adressen.

RARP: Reverse Address Resolution Protocol. Dient der Zuordnung IP-Adressen zu MAC-Adressen (veraltet – ersetzt durch BOOTP)

RIP: Routing Information Protocol. Informationsaustausch zwischen Routern (Distanzvektor) via UDP

Transportschicht 4: TCP: Transmission Control Protocol. Übertragung von

Datenströmen (verbindungsorientiert, zuverlässig). UDP: User Datagram Protocol. Übertragung von

Datenpaketen (verbindungslos, unzuverlässig, geringer Overhead)

SCTP: Stream Control Transmission Protocol. Transportprotokoll

Anwendungsschicht 5 – 7: HTTP: Hypertext Transfer Protocol (www). HTTPS: Hypertext Transfer Protocol Secure. FTP: File Transfer Protocol SMTP: Simple Mail Transfer Protocol. Mailversand POP3: Post Office Protocol v.3. Mailabruf Telnet: unverschlüsseltes Login auf entfernten Rechnern

(remote terminal)

DNS: Domain Name Service. Umsetzung von Domainnamen zu IP-Adressen.

SNMP: Simple Network Management Protocol. Verwaltung von Geräten im Netzwerk.

SSH: Secure Shell. Verschlüsseltes remote terminal.

ANDERES

File Access mit Linux: #include <stdio.h>, #include <fcntl.h> /* … */ char buffer[1024]; fd = open(“file.txt”,O_RDONLY); //-1 on failure numbytes_read = read(fd, &buffer, buffer_length); //-1 on fail Speicher-Kenndaten:

TODO

Todo: Stack frame Aufbau (2.1 S. 25) graphik network layers VFS Bild aus Besprechung

Prüfung: - ‚open book‘ - nichts elektronisches (ausser TR Batterien!) - 3 Stunden, schriftl., 3 Aufg. TIK I und 3 Aufg. TIK II = 6 Aufg.

Typische Aufgaben: - Grösse von file systemen berechnen - Hard disk zeiten berechnen ist Standardaufgabe

o versch. Scheduling algos kennen!