Philip MasserMartin Dobler

Mathias RiederFlorian Reischer

Christian GmeinerChristian Hämmerle

Architekturentwurf

Überblick

Beispielapplikation Architekturentwurf Kernel Treiber und Server Bootprozess Scheduling Interprozesskommunikation Swapping

Organisatorischer Rückblick Planung weiterer Schritte

Beispielapplikation

Digitaler Bilderrahmen Anzeigen von Bitmapbildern auf SD-Karte Abspielen von Hintergrundsound von SD-Karte Steuern der Bilderabfolge durch Tastendrücke

_ Vorwärts_ Rückwärts_ Slideshow

Architekturentwurf

Rechte von Prozessen

3 Privilegienstufen

Kernel darf alles

Unprivilegierte Prozesseo eingeschränkte SysCall APIo kein Zugriff auf Hardware

Priviligierte Prozesseo volle SysCall APIo können Privilegien vererbeno können andere Prozesse beenden

Kernel

Mikrokernel Kommunikation aus oberen Schichten via SYSCALLS (static

LIB) Mehr Stabilität und Flexibilität in den oberen Schichten

HAL

Für jede Architektur existiert eine eigene HAL

Funktionen für den Kernelo Ein- bzw. Ausschalten einer Interruptquelleo Hardwaretimer-Interface für Schedulero Fault-Handler für unkontrollierte Exceptions

Funktionen für die Treibero Registrierung auf Hardware-Interruptso IO-Zugriff direkt auf Registero Automatisches PIO Setup für LEDs und Tastero Information über Devices und deren Ressourceno Schnittstelle für DMA

Treiber und Server

Treiber und Server meist ein Prozess Kommunikation mit Servern mittels SERVICE CALLS Treiber kommunizieren mit Kernel mittels SYSCALLS Möglichst komfortable API für den Programmierer (static

LIB)

Sound Server und Treiber

Treiber und Server sind ein Prozess Schnittstelle zum Sound-Chip und dem Audioausgang Kein Buffering und Prefetching

- LOAD(FILENAME)

- PLAY()

- PAUSE()

- STOP()

- SETVOLUME(LEVEL)

Bootprozess

1. startup_init (Generelles Hardware-Setup)2. int main des Kernels

1. HAL initialisieren2. InterruptHandler / Clock / Scheduler starten3. IPC und Memory Management initialisieren4. InitProcess starten

1. Treiber/Server starten2. Eingebaute Programme starten

(Shell…)

Scheduling

Anforderungen an den Scheduler

Minimale Latenzzeit(Antwort bzw Jobfertigstellungszeit)

Maximaler Jobdurchsatz Maximaler Ausnutzungsgrad

(I/O-Geräte müssen maximal ausgenutzt werden) Fairness

(Jeder Job bekommt Ausführungszeit, keiner verhungert)

Scheduling

Verfahren in Anlehnung an Round Robin Viele Prozesse in RUNNABLE Status Welcher Prozess wird ausgeführt, wenn Prioritäten benutzt

werden? 0 RUNNABLE Prozesse: Starvation

(Abhilfe durch IDLE Prozess) 1 RUNNABLE Prozess: Einfach > 1 RUNNABLE Prozesse: ?

Dead

RunnableRunning Dead

Blocked Zombie

Scheduling

Präemptives Round Robin mit mehreren Queues für Prioritäten Clock gibt Ticks über Interrupt Quantum muss festgelegt werden

o Tradeoff: Responsiveness vs. Scheduler Rechenzeito Tannenbaum empfiehlt 100ms

HIGH-Priority P P P P P P P P P P P

LOW-Priority

P P P P P P P P P P P

P P P P P P P P P P P

.

.

.

7 /10

2 /10

1 /10

Scheduling

Speicherbedarf abhängig vono Maximaler Anzahl Prozesseo Anzahl Queues

Bei max. 256 Prozessen und drei Queueso 23.5 KB (24098 Bytes)

Bei max. 64 Prozessen und drei Queueso 6 KB (6050 Bytes)

Scheduling

Aufwände für Operationen

Anlegen eines neuen Prozesseso Maximal O(Anzahl Prozesse)o Mininmal Ω(1)o In der Regel: O(Anzahl Prozesse / 2)

Reschedulingo O(Anzahl der Prozesse)

Jedoch Zugriff auf Prozesse, Prozessswitches etc O(1)

Scheduling

Problem ?

Abhilfen Response Ratio berechnen Gewichtung der Prioritäten nach Anzahl Prozesse in der

Queue

Scheduling und Echtzeit

Verfahren für harte Echtzeit scheinen nur wenig relevanto Rate Monotonic Schedulingo Deadline Monotonic Scheduling

optimiert für periodische Prozesse (Periodendauer = Deadline)

Lösung: RoundRobin welches die Ideen von Highest Response Ratio Next verwendet

Highest Response Ratio Next

Priorität wächst proportional zur Response Ratio

LaufzeitWartezeitLaufzeit

rtwtrtrr

t1 4 7 10 13 16 19 22 25 28 31 34

0

1

2

3

4

5

6

runningrr=

Interprozesskommunikation

Grundsatzentscheidung: Shared Memory oder nicht?

Shared Memory ist schnell aber gefährlichMicrokernel soll Stabilität bringen,deshalb wollen wir auch ein stabiles IPC

Lösung: Named Pipes

Simples IPC SoundServer.SetVolume

Simples IPC SoundServer.SetVolume

Simples IPC SoundServer.SetVolume

Nachteil des simplen IPC sind die zahlreichen Syscalls

Wie können wir Syscalls einsparen und die Kommunikationzwischen den Prozessen beschleunigen?

IPC mit PipesSoundServer.SetVolume

IPC mit PipesSoundServer.SetVolume

Pipe Datenstruktur

Durch geschickte Wahl der Datenstruktur einer Pipe kann auf ein

Synchronisiertes Lesen verzichtet werden:

LA A0 A2 A3 ...

read-pointer write-pointer

Länge der Message A

Message A

read-pointer erst NACHLeseoperation erhöhen.

Prozess kann unterbrochen werden, kein

Überschreiben

B2 B3 4 B0... B1

::

Ring-Array

- Overhead durch Länge der Message+ Synchronisieren beim Lesen fällt weg

Interrupt Handling

Hardware-Interrupts werden vom Kernel verwalteto Treiber können sich auf Interrupt request-# registriereno Tritt Interrupt auf, wird dieser vom Kernel über IPC an

den jeweiligen Treiber geschickto Kernel quittiert Interrupt

Ausnahme: Interrupts für Clock-Treiber für Schedulero Interrupt wird in der HAL abgehandelt und eine

Callback Methode im Kernel aufgerufen.

Interrupt Handling

Swapping

Problem: Wer übernimmt Swapping/Paging in einem Microkernel

KernelWann (Page fault)Wie (Strategie: z.B.: Least Recently Used)

SD-TreiberPhysikalisches Schreiben und Lesen der PagesDarf nicht ausgelagert werden

Kommunikation über IPCAuszulagernde Page (SD-Queue)Zu ladende Page (SD-Queue)Kernel (Scheduler) übergibt dem SD-Treiber die CPU

Organisatorischer Rückblick

Wöchentliche Dienstagsmeetingso Review der Ergebnisse aus letzter Wocheo Besprechung der Wiki-Artikelo Problembereiche identifiziereno Detailresearcho Diskussion in der Gruppeo Neue Aufgabenverteilung für die kommende Woche

Research und Lösen der Aufgaben in Heimarbeit(ggf. in Partnerarbeit falls Themen und Aufgaben verwandt sind)

Organisatorischer Rückblick

Archivierung der Artikel und Ergebnisse mittels Wiki imPM-System www.assembla.com

Historisierung der Artikel Tickets, Tasks, Messaging Service Zeiterfassung Subversion für Source Code und Präsentationen, Grafiken… Automatische Email-Generierung an alle/bestimmte

Mitglieder

Planung weiterer Schritte

Timebox 2 (bis 9.12.) Implementierung des Betriebssystemkerns Vollständiger Kernel, RS232 Server und Shell Geschätzter Implementierungsaufwand 201 Stunden

Timebox 3 (bis 20.01.) Implementierung der Treiber und Server, Beispielapplikation und

erweiterte Funktionalitäten (DMA, Swapping…) Geschätzter Implementierungsaufwand 225 Stunden