FHNW: bsys

Jeder Prozess ist im OS als ein Process Control Block (PCB) repräsentiert.

Ein PCB beinhaltet folgende Informationen:

• Process State: Status des Prozesses
• Program Counter: Instruction Pointer (hält die Adresse der nächsten Instruktion die vom Prozess ausgeführt wird)
• CPU Register: Stack Pointers, General Purpose Registers, etc. (architekturabhängig)
• CPU Scheduling Information: Priorität und Pointers zu Scheduling Queues.
• Memory Management Information: Limiten von Registern und Page Tables, etc.
• Accounting Information: CPU, Real Time, Time Limits, Process Number, etc.
• I/O Status Information: Liste von I/O Devices, offenen Dateien die vom Prozess verwendet werden.

Wenn ein Prozess:

• warten muss (z.B.auf I/O oder einen Event)
• seine zugeordente Laufzeit oder andere Resourcengrenzen erreicht oder überschreitet
• terminiert oder gestoppt wird
• die CPU freiwillig abgibt

muss das OS die CPU einen anderen ablaufbereiten Prozess zuteilen und diesen starten.

Dabei muss der exakte Prozesszustand für das spätere Restaurieren abgespeichert werden.

Dieser Vorgang ist purer Overhead, weil während dem Wechsel das System keine sinnvolle Arbeit erledigt. Kontextwechsel sind eine “schwere” Operation mit viel Verarbeitungsaufwand durch den Kernel.

• Running und Waiting werden hier in weitere Zustände aufgeteilt.

• fork: Erstellen eines neuen Prozesses. Dabei wird der Adressraum des Parents kopiert. Dies ermöglicht eine einfache Kommunikation mit dem Child.
• exec: Ausführen des Prozesses
• Signal: Stoppen eines Prozesses
• exit: Terminieren eines Prozesses
• wait: Warten auf das Terminieren, einfache Synchronisation

Ein Prozess kann aus mehreren Threads bestehen. Dabei wird der Process Control Block (PCB) erweitert, so dass sie Informationen über jeden Thread hat.

Kontextwechsel sind schwere Operationen. Durch Threading können die Anzahl Kontextwechsel reduziert werden, weil sie den gleichen Context teilen. Von Thread 1 zu Thread 2 wird kein Kontextwechsel benötigt. Das Scheduling muss innerhalb des Prozesses erfolgen und ist somit Aufgabe des Programmierers. Er muss sich selbst um die Datenintegrität kümmern.

Die Einträge in der Process Table sind die Process Control Blocks.

Virtual Memory separiert die logische Memory, wahrgenommen durch den User, vom physischen Memory. 

• Erweiterung des Hauptspeichers pro System (mehr Prozesse im System als Speicher verfügbar), oder pro Prozess (einzelner Prozess grösser als verfügbarer Hauptspeicher)
• Organisation des Hauptspeichers in gleich grosse einheitliche addressierbare Einheiten  (Seiten/Pages).
• Benötigt hardware-unterstützte Abbildung zwischen physischen  und virtuellen Adressen (Statische Tabelle, etc.)

Every process is given the impression that it is working with large, contiguous sections of memory. Physically, the memory of each process may be dispersed across different areas of physical memory, or may have been moved (paged out) to another storage, typically to a hard disk drive.

Das Virtual Memory verwendet Page Table als Datenstruktur, um das Mapping zwischen virtuellen Adressen und physischen Adressen zu speichern. Die virtuellen Adressen werden vom Prozess verwendet. Hardware verwendet die physische Adressen (RAM Subsysteme). Es ist die Aufgabe des OS, die virtuelle Adresse, welche es vom Prozessor erhält, in eine physische zu mappen, damit der Prozess die Daten aus dem Memory erhält.

Beim swap out werden Prozesse vom Hauptspeicher in Swap Device ausgelagert.

1. Kein Platz im HS für weitere Prozesse, aber Prozess ruft fork auf: fork swap
2. Kein Platz im HS, aber Prozess wächst, z.B. weil der Stack wäckst: expansion swap
3. Auf Swap Device ausgelagerter wartender Prozess wird ready to run und wird vom Scheduler ausgewählt: exchange swap
   1. Zombie Prozesse und "locked in memory" Prozesse sind nicht wählbar
   2. Schlafende Prozesse werden ready to run Prozesse vorgezogen
   3. Präferenz auf Prozessen mit niedriger Priorität
   4. Präferenz auf Prozessen die > 2 sec. im HS waren

Verlagere Prozesse vom Swap Device in den Hauptspeicher

• Nur ready to run Prozesse sind wählbar
• Präferenz auf Prozessen die > 2 sec ausgelagert waren.

In a system that uses demand paging, the operating system copies a disk page into physical memory only if an attempt is made to access it and that page is not already in memory. It follows that a process begins execution with none of its pages in physical memory, and many page faults will occur until most of a process's working set of pages is located in physical memory.

• Lokalität des Codes, nur etwa 10-15% des Programmcodes müssen zu jeder Zeit beliebigen Zeit im HS liegen ("working set")
• Zugriff auf eine Seite ausserhalb des working set führt zu einem page fault (Seitenladefehler), dann wird die Seite nachgeaden.
• Optimierungen des demand paging durch:
  • Reference Bit: Ermöglicht nicht-lineares working set
  • Age Bits: verbleibende Zeitt einer Seite im working set
• Aufgaben des Paging-Subsystems:
  • Seitenalterung und Auslagerung/Löschung von genügend alter Seiten
  • Bearbeitung von page faults

Ein terminierter Prozess, wobei der Parent noch nicht wait() aufgerufen hat, wird zu einem Zombie Prozess. Der Prozess erscheint weiterhin in der Prozesstabelle. Jeder Prozess der sich terminiert ist für eine kurze Zeit ein Zombie.

Falls er zu einem orphan wird (Parentprozess hat sich terminiert, ohne wait zu callen), setzt er init als neuer Parent des orphan. init führt periodisch wait() aus, wobei sich der orphan auflöst.

Swapper erkennt nach dem swap in, dass ein Prozess noch nicht laufen muss...also swapped er ihn wieder aus.

A page fault (sometimes called #PF or PF) is a type of interrupt, called trap, raised by computer hardware when a running program accesses a memory page that is mapped into the virtual address space, but not actually loaded into main memory.

• Occurs whenever a process accesses a logical page that is not currently resident in physical memory
• MMU (Memory Management Unit) causes a trap (interrupt), resulting in a context switch to the OS paging mechanism (Swapper)
• Swapper loads missing page from disk, possibly moving another page from memory to disk if necessary

Ziel: Optimierung des Zugriffs auf block-orientierte Geräte, maximale Menge Daten im Speicher behalten.

• Strategie 1: read ahead
  Vorteil: Beschleunigt das sequentielle Lesen
  Risiko: potentielle Verschwendung von Hauptspeicher
   
• Strategie 2: delayed write
  Vorteil: Bündeln von Daten in Blöcke für das Schreiben auf langsame Geräte
  Risiko: Nach einem erfolgreichen write() sind Daten noch nicht auf der Disk gespeichert.

In Unix werden Interrupts immer im Kontext des gerade
laufenden Prozesses behandelt, auch wenn der Prozess
den Interrupt nicht verursacht hat oder nicht davon
profitiert. Der gerade laufende Prozess muss also seine
Arbeit unterbrechen, den Kontext sichern, den Interrupt
behandeln, den Kontext restaurieren und kann dann
weiterarbeiten.

Ein Prozess Scheduler regelt die zeitliche Ausführung mehrer Prozesse.

Mögliche Strategien:

• First In First Out (FIFO)
• Round Robin
• Priority Scheduling

• Single- / multi-tasking
• Single- / Multi-user
• Embedded
• Real-time
• Distributed

Ein Prozess der keine CPU-Time erhält, weil der Scheduling Algorithmus den Task ignoriert. Der Algorithmus sollte so programmiert sein, dass alle Prozesse Chancen auf Resourcen haben.

Beispiel: File Transfer schlechter priosiert und die Gegenseite schickt ein Timeout, weil der Prozess keine Zeit erhalten hat um die Daten zu übermitteln.

Dies geschieht wenn zwei Prozesse nichts tun, aber auf einander warten.

• Prozesse kreieren
• Prozesse starten
• Prozesse schedulen, Warteschlangen, Resourcenverbrauch
• Prozesse stoppen / unterbrechen
• Prozesse terminieren (freiwillig / wegen Fehler)
• Prozesskommunikation (Prozess-Prozess und Kern-Prozess zu Prozesskern)
• Zuordnung von Hauptspeicher und anderen geteilten Resourcen
  Prozesse wachsen während der Laufzeit, dass muss berücksichtigt werden.
• Ein-/Auslagerung von Prozessen (Swapping: Prozess auf Disk auslagern)
• Prozesse und ihre Zustände anzeigen

Auslagerung von Prozess aus dem Hauptspeicher auf die Disk. Der Swapper wird vom Kernel (Process 0) aufgerufen.

Der Prozess lebt nicht mehr im Hauptspeicher aber auf der Disk. Damit wurde Platz geschaffen im RAM. Dies kann wieder ins RAM geladen wird.

Es gibt noch andere Strategien.

• Einzige Schnittstelle zwischen Kern und Benutzer
• Normierung der Syntax & Semantik
• Parametrisierung und Übergabe
• Übergabe der Kontrolle
   
• Sollte Rückwärtskompatibel sein
• Linux hat ungefähr 450 Funktionen

• Die Fähigkeiten der Hardware optimal ausnutzen (z.B. Mehrprozessor-Architektur)
• Die Komplexität und Inhomogenität der Hardware und Peripherie verbergen (z.B. einhetlicher Systemaufruf für Daten Lesen und Schreiben)
• Die Hardware und Peripherie vor unerlaubter Nutzung schützen (Bypassing SCI).
   
• Gewisse Aufgaben können bereits von der Hardware übernommen werden. Falls nicht, müssen Module für den Kern oder Treiber der Hardware mitgeliefert werden, um diese Aufgaben zu erfüllen. 

• Dateien, Directories
• Prozesssynchronisation (Lock Files)
• Prozesskommunikation (Pipes, Sockets)
• Peripheriegeräte (Device Special Files)
• Kommunikationsprotokolle (TCP/IP)
• Prozesse (/proc Dateissystem)
   
• Der Kern übernimmt die Aufgabe, um mit dem Device zu kommunizieren, in dem er das entsprechende File öffnet und bearbeitet (schreiben)

1. SCI
2. Kernel und ihre Subsysteme
   Dazwischen existiert in der Regel auch eine Schnittstelle. udev wird heuzutage auf Linux verwendet (depreciated: Hardware Abstraction Layer)
3. Hardware

Subsysteme von Unix

• Konsistente, permanente Ablage von Dateien
• Strukturierung der Ablage (Hierarchie, Extensions)
• Zugriffssicherheit (Rechte/Rollen, Attribute)
• Basisoperationen (Navigation, Dateimanipulationen)
• Programmierbarer Zugriff
• Mehrbenutzer/-prozessfähigkeit
• Performance
• Standardisierung

Eine Parition kann in Block Groups aufgeteilt werden. Jede Group besteht aus den folgenden Teilen:

• Superblock
• Group Description
• Block Bitmap
• Inode Bitmap
• Inode Table
• Data Blocks

• Ein Superblock beinhaltet die Verwaltunginformationen eines Dateisystems. Sie wiederspiegelt den Zustand des Filesystems. Folgende Informationen sind darin abgespeichert:

• Größe des Dateisystems
• Anzahl freier Blöcke
• Zeiger auf Liste der freien Blöcke
• Zeiger auf den ersten freien Block in der Liste der freien Blöcke
• Größe der Inode-Liste
• Anzahl freier Inodes
• Zeiger auf Liste der freien Inodes
• Zeiger auf den nächsten freien Inode in der Liste der freien Inodes
• Sperr-Felder für Liste der freien Blöcke / Inodes (zum Beispiel für defekte Blöcke)
• Anzeigefeld, ob Superblock verändert wurde

Durch vordefinierte Formeln. Da Blöcke und Inodes in der Regel gleich gross sind, können Formeln eingesetzt werden. Eine solche Referenzierung ist schnell. Alternativen wäre eine Art Datenbank oder Hash-Maps zu verwenden, um die korrekten Referenzen zu finden. Diese sind allerdings schwerfällig bei der Wartung und langsamer bei der Referenzierung.

• namei: Wandelt Pfad in inode Nummer um
• iget / iput: Lesen und Schreiben für inode
• ialloc / ifree: Allozieren und Freigeben von Inode
• alloc / free / bmap: Allozieren und Freigeben von Datenblöcken

Ist eine Methode um die allozierten Blöcke zu verfolgen.

Falls das OS eine Datei schreiben muss, scant es die Bitmap und sucht solange, bis es genügend Blöcke gefunden hat, um die Datei zu speichern. Eine 0 indiziert, dass der Block verfügbar ist. Eine 1 markiert diese als alloziert.

Ein Inode enthält Meta-Informationen einer Datei, sowie dessen Adressen (direkt/indirekt) auf der Disk. Inodes sind alle gleich gross.

• Art der Datei (regular, directory, symbolic link, etc.)
• UID + GUID
• Zugriffsrechte
• Access-, Modify- (file) und Change (Inode) time stamp
• Anzahl Links (Hardlink counter)
• Grösse der Datei
• Verweise auf die Datenblöcke (Adressen). Es existieren direkte, sowie einfache, zweifache und sogar dreifache Verweise auf Datenblöcke.

Wichtig: Das Inode speichert den Filename NICHT ab. Aus diesem Grund können mehrere Links von der gleichen Datei existieren, ohne den Inhalt kopieren zu müssen.

Change timestamp wird manipuliert, wenn sich die Informationen im Inode ändern (chown, links). Der Modify timestamp ändert sich wenn am Inhalt etwas geändert wird. Es kann vorkommen, dass beide Timestamps geändert werden.

• Boot Block
  Enthält das Startprogramm (Bootloader), welcher ins RAM geladen wird, um in der Regel das Betriebssystem zu starten.
   
• Super Block
  Dieser Teil speichert diverse Verwaltungsinformationen ab
  • Grösse des Dateisystems
  • Anzahl freier Blöcke
  • Grösse der Inode-Liste
  • Anzahl freier Inodes
  • etc.
     
• Inode Liste
  Liste aller Inodes die auf bestimmte Datenblöcke zeigen. Ein Inode beinhaltet Meta-Informationen einer Datei.
   
• Data Block
  Diese speichern den eigentlichen Inhalt einer Datei ab. Sie ist auf eine festgelegte Anzahl Bits/Bytes limitiert. Ein grösseres File verteilt sich also auf mehrere Datenblöcke.

• Anzahl Disks & Controller
• Verteilung auf Partitionen
• Blockgrösse pro Partition
  • Grosse Blöcke: schneller Zugriff auf Dateien (Durchschnittsgrösse < 4kB)
  • Kleine Blöcke: weniger interne Fragmentierung
• Anzahl Dateien / Inodes pro Partition
  • Wenige Inodes: Mehr Platz für Dateiblöcke
  • Viele Inodes: Mehr Dateien pro Partition möglich

Ein Filesystem, dass vor allem grössere Dateien (Filme, z.B.) abspeichert, sollte grössere Blöcke haben, um die Performance zu verbessern. Dasselbe gilt in die umgekehrte Richtung wenn vorwiegend kleinere Dateien abgespeichert werden. Wenn nicht optimal genutzt, verschwendet man Platz in den Blöcken oder hat zu viele kleine Blöcke, was den Zugriff verlangsamt.

Gerätedateien werden als Schnittstelle zwischen Gerätetreibern oder Systemkomponenten und Anwendungsprogrammen, die im Usersprace (CPU Kreis) ablaufen, genutzt. Diese befinden sich unter /dev/. Bei der Auflistung werden Major- (Typ) und Minornummern (Nummerierung des Typs) dargestellt. Diese dienen zur Identifikation. Es wird zwischen block- und zeichen-orientierte (c) Geräte unterschieden.

$ ls -l /dev/sda
brw-rw---- 1 root disk 8, 0 Jul 12 15:54 /dev/sda

Die Zugriffsrechte auf diese Dateien sind relevant. Es gibt auch sogenante Virtuelle/Pseudo-Geräte. /dev/null z.B.

• Block Devices übertragen Daten in Datenblöcke und werden oft für parallele Datenübertragungen genutzt. Diese Devices speichern in der Regel Daten (Harddisks, Diskette, CD-Rom). 
• Character Devices übertragen ein Zeichen (Byte) zur selben Zeit, sind also der seriellen Datenübertragung zuzusprechen. Dazu gehören Devices wie Maus, Drucker, etc.

Es kann vorkommen, dass ein Device beiden Typen entspricht.

• Read
• Write
• Execute
• Append (common)
• Delete (common)
• List (common)
• Rename (complementary)
• Copy (complementary)
• Edit (complementary)

Die untersten drei werden oft von Systemprogrammen übernommen, welche Low-Level Systemcalls machen. Nur die ersten drei existieren in Unix normalerweise.