Seite 1

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Inhalte

bull Eigenschaften von Rechenprozessen (Tasks)bull Taskuumlbergaumlnge (process control block)bull Multitasking (kooperativ und praumlemptiv)bull Schedulerbull Erzeugen Starten und Beenden von Tasksbull Taskzustaumlnde (running suspended runnableready dormant)bull Tasks und Threadsbull Zeitparameter von Tasks Periode Antwortzeit Ausfuumlhrungszeit Spielraum hellip

Seite 2

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Task = Rechenprozess bull Ein Rechenprozess ist ein von einem Echtzeit-Betriebssystem gesteuerter Vorgang der

Abarbeitung eines sequenziellen Programmsbull Rechenprozess beginnt mit Eintrag in eine Liste des Echtzeit-Betriebssystems und

endet mit dem Loumlschen aus dieser Listebull Rechenprozess existiert nicht nur waumlhrend der Ausfuumlhrung der Befehle sondern auch

waumlhrend geplanter oder erzwungener Wartezeitenbull Rechenprozess benoumltigt BetriebsmittelRessourcen (CPU-Zeit Speicherplatz Zugriff

auf EA-Geraumlte) und ist selbst ein Betriebsmittel das vom Betriebssystem (BS) verwaltet wird (Erzeugung Terminierung Scheduling )

bull Ein Prozessor fuumlhrt in jeder Zeiteinheit maximal einen Rechenprozess ausbull Laufen mehrere Prozesse auf einem Rechner finden Prozesswechsel statt Das

Betriebssystem entscheidet welcher Prozess zu welchem Zeitpunkt ausgefuumlhrt wirdbull Rechenprozesse sind gegeneinander abgeschottet ndash jeder besitzt (virtuell) seine

eigenen Betriebsmittel wie etwa den Adressraum Das BS sorgt fuumlr diese Abschottung

Seite 3

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Eigenschaften von Rechenprozessen

Ein Rechenprozess wird durch folgende Eigenschaften beschriebenbull Eine Folge von Maschinenbefehlen die durch das ausgefuumlhrte Programm (program

code text section) festgelegt sindbull Der aktuelle Zustand der Bearbeitung ist durch den Programmzaumlhler und die

Registerinhalte des Prozessors beschrieben (internal state)bull Der Inhalt des Stapelspeichers auf dem temporaumlre Variablen und Parameter fuumlr

Funktionsaufrufe verwaltet werden (stack)bull Der Inhalt des Speichers in dem die globale Daten des Prozesses gehalten werden

(data section)bull Beziehungen zu anderen Betriebsmitteln wie zB geoumlffnete Dateien (external state)

Seite 4

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesskontrollblock (PCB)bull Ein Prozess wird im Betriebssystem durch einen Prozesskontrollblock

(Prozessleitblock) repraumlsentiert in dem alle Informationen zu einem laufenden Prozess verwaltet werden

bull Beispiel fuumlr Informationen in einem PCB

Seite 5

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Multitasking bezeichnet die Faumlhigkeit eines Betriebssystems mehrere Aufgaben (Tasks) nebenlaumlufig auszufuumlhren Dabei werden die verschiedenen Prozesse in so kurzen Abstaumlnden immer abwechselnd aktiviert dass der Eindruck der Gleichzeitigkeit entsteht

bull Optimiert die Prozessor-Auslastung und verringert die Prozessor-Wartezeitbull Prozess ist ein bdquoProgramm in Ausfuumlhrungldquo

ndash Speicherabbild eines gestarteten Programms mit den vom Betriebssystem benoumltigten Systemdatenndash alle Prozesse laufen isoliert voneinander ab so dass die Prozesszustaumlnde vor der Unterbrechung gespeichert

werden muumlssenbull Voraussetzung

ndash Ein Timer-Interrupt wird in regelmaumlszligigen Abstaumlnden an die CPU geschicktndash Die zugehoumlrige Interrupt-Service-Routine loumlst den Scheduler (Prozessverwalter) aus

bull Kooperatives Multitasking (DOS Windows 31)ndash Scheduler uumlberlaumlsst Prozessen die Zuteilung von CPU Zeitndash Vorteil geringer Verwaltungsaufwand noumltig Nachteil fehlerhafter Prozess blockiert alle anderen

bull Praumlemptives Multitasking (Windows NT)ndash Scheduler verwaltet Liste aller aktiven Prozesse Reihenfolge entscheidet uumlber Dringlichkeit Aufbau der Listen

nach verschiedenen Prinzipienndash Unterbrechungen jederzeit moumlglich

Seite 6

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Kooperatives Multitasking

bull Jeder Prozess gibt seinen Status freiwillig an naumlchsten Prozess weiterbull Wenn Prozess 1 fertig ist gibt er dies an Prozess 2 weiter und

wechselt in den Status rechenbereit waumlhrend der Prozess 2 von rechenbereit auf rechnend wechselt

bull Bsp Eine Runde von Indianern die die Friedenspfeife rauchtbull Jeder Indianer in diesem Kreis stellt einen Prozess (alle rechenbereit)

dar und die Friedenspfeife stellt Rechenzeit dar

bull Rauchender Indianer entspricht dem Zustand rechnend alle anderen Indianer sind rechenbereit da sie auf die Pfeife warten

bull Das Kooperative an diesem System ist dass jeder Indianer nachdem er eine Weile geraucht hat die Pfeife freiwillig an den naumlchsten Indianer weitergibt

bull Hieraus wird auch der Nachteil des Systems sichtbar Kann oder will ein Indianer die Pfeife nicht weiterreichen kommt das System zum erliegen

bull Vorteil leicht implementierbar

Seite 7

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Praumlemptives Multitasking

bull Jedem Prozess wird bestimmtes Zeitfenster gegeben in dem er ausgefuumlhrt wird am Ende der Zeit wird der Prozess unterbrochen

bull Teil des Betriebssystems kuumlmmert sich um Wechseln zum naumlchsten Prozess und gibt dem naumlchsten auszufuumlhrenden Prozess die Kontrolle bis zum Ende des Zeitfensters

bull Bsp Haumluptling nimmt selbst die Pfeife in die Hand und reicht sie von Indianer zu Indianer weiter ohne sie aus der Hand zu geben

bull Da sich keiner zu widersprechen getraut ist der ordnungsgemaumlszlige Ablauf sichergestellt

bull Haumluptling fungiert als Interrupt der regelmaumlszligig ISR (Interrupt Service Routine sbquoPfeife weiterreichenrsquo aufruft

bull Dann gibt er dem jeweiligen Indianer der nun rauchen darf den Status running bis er ihn wieder unterbricht

bull Nachteil des Systems mehr Programmieraufwand

bull Vorteil stabil funktionierendes System

Seite 8

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Schedulerbull Bestandteil des Betriebssystemsbull sinnvolle Verteilung der CPU Zeit an aktive Prozessebull verantwortlich fuumlr die Umsetzung von Multitasking

Ziele des Schedulers (die sich jedoch im Einzelfall widersprechen koumlnnen) bull Fairness jeder Prozess soll einen gerechten Anteil an der CPU-Leistung bekommen dh

kein Prozess wird dauerhaft benachteiligtbull Effizienz CPU sollte dauerhaft belegt werdenbull Antwortzeit Antwortzeit soll fuumlr interaktive Benutzer minimal seinbull Durchsatz Anzahl der bearbeiteten Prozesse pro Zeitintervall soll maximiert werden (=

die zur Verfuumlgung stehenden Ressourcen sollen optimal ausgelastet werden)bull Verweilzeit Verweildauer von Programmen soll moumlglichst gering seinbull Terminerfuumlllung Prozesse die zu einem bestimmten Termin beendet sein

muumlssen werden so geplant dass der Termin eingehalten wird

Seite 9

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Erzeugen von Prozessen bull Prozesse werden erzeugt bei

ndash Initialisierung des Systems (einfache Systeme zB Steuerung eines Mikrowellenherds)

ndash Systemaufruf zum Erzeugen eines (Sohn-)Prozesses durch einen anderen (Vater-)Prozess

ndash Benutzeranfrage einen neuen Prozess zu erzeugenndash Initiierung einer Stapelverarbeitung (Batch-Job)

bull POSIX-Systeme benutzen hierzu den fork() Systemaufrufndash Der neu erzeugte Prozess (child) ist eine exakte Kopie des erzeugenden Prozesses (parent)

besitzt aber eine neue Prozessnummerndash Beide Prozesse fuumlhren dieselben Instruktionen nach dem fork() ausndash Der Ergebniswert des fork() Systemaufrufs ist in beiden Prozessen unterschiedlichndash Mittels des Systemaufrufs exec() koumlnnen in einem Prozess neue Programme gestartet

werden

bull Windows Systemaufruf CreateProcess()bull Da beliebige Prozesse neue Prozesse erzeugen koumlnnen entsteht eine Hierarchie

(Baum) von Prozessen die als verkettete Liste organisiert ist(POSIX = Portable Operating System Interface (Standard-Schnittstelle zw Applikation und Betriebssystem)

Seite 10

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Beenden von Prozessen bull Prozesse koumlnnen sich selbst durch den exit()-Systemaufruf beenden und damit aus

dem System entfernenbull Ein Prozess kann die von ihm erzeugten Prozesse beenden falls

ndash ein Prozess die ihm zugestandenen Betriebsmittel verbraucht hatndash ein Prozess nicht laumlnger gebraucht wird oder fallsndash der erzeugende Prozess sich beendet und es nicht gewuumlnscht oder erlaubt ist

dass die erzeugten Prozesse unabhaumlngig weiter existieren (cascading termination)bull Auf die Beendigung eines erzeugten Prozesses kann in POSIX-Systemen mit Hilfe des

wait() Systemaufrufs gewartet werdenbull Der Ergebniswert (return code) eines sich beendenden Prozesses wird an den

erzeugenden Prozess weitergeleitet

Seite 11

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

while (1) repeat forever type_prompt() display prompt on screen read_command() read input from the terminal

pid = fork() create a new

process if (pid lt 0) repeat if system call failed

perror(fork)continue

if (pid = 0) parent process

waitpid(pid ampstatus 0) wait for child

else child process execve(command params 0) execute

command

Beispiel einfacher Kommandointerpreter

als Sohnprozessals Vaterprozess

Seite 12

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Die 5 Taskzustaumlnde mit den wichtigsten Uumlbergaumlngen

dormant existent

ready bereit

running laufend terminated

beendet

suspended blockiert

Task ist der Prozessverwaltung bekannt gegeben

Task ist gestartet und alle Betriebsmittel vorhanden (eingeplant)

Betriebsmittel fehlen

Weitere Begriffe

Dormant = idle new

Existent = ruhend

Ready = runnable busy

Bereit = ablaufwillig rechenbereit

Running = executing

Laufend = ablaufend rechnend aktiv

Suspended = blocked waiting

Task ist abgearbeitet

Task ist eliminiert

Betriebsmittel vorhanden

Task ist der Prozessor zugeteilt

Task ist verdraumlngt

Seite 13

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Die 5 Taskzustaumlnde mit den wichtigsten Uumlbergaumlngen

dormant existent

ready bereit

running laufend terminated

beendet

suspended blockiert

admitted

IO or event wait

exit

Task ist eliminiert

IO or event completion

dispatch Interrupt trap

Seite 14

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Zustandsuumlbergaumlnge (Umhaumlngen in eine andere Liste) bull Es existieren drei Arten des Prozessor-Entzugs

ndash Aufgabe des Prozessors durch einen Warteaufruf Wartelistendash Verdraumlngung durch einen anderen Prozess (Praumlemption) Bereitlistendash Beendigung

bull Vom Zustand bdquoblockiertldquo geht es nicht direkt in den Zustand bdquorunningldquobull Der Uumlbergang von bdquorunningldquo nach bdquoblockiertldquo wird immer durch den Prozess selbst

initiiertbull Der Uumlbergang von bdquorunningldquo nach bdquobeendetldquo wird immer durch den Prozess selbst

initiiertbull Der Uumlbergang von bdquobereitldquo nach bdquorunningldquo und zuruumlck geschieht immer durch das

Betriebssystem

Seite 15

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Leichtgewichtsprozesse (Threads)bull Threads sind parallele Kontrollfluumlsse die nicht gegeneinander abgeschottet sind

ndash laufen innerhalb des Adressraums eines bdquoechtenldquo Rechenprozessesndash teilen sich gemeinsame Ressourcen (zB globale Variable)

bull Es gibt Threads im Betriebssystem-Kernel Scheduling durch BSbull Es gibt Threads im Usermodus des Betriebssystems Scheduling durch Anwendung

BS nur fuumlr Prozess-Scheduling verantwortlich

Kernel

Usermodus

Prozess

Thread

Seite 16

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Unterschiede zwischen Tasks und Threads

bull Aus Sicht der Betriebszustaumlnde der Zeitparameter des Schedulings und der Synchronisation sind Thread und Task gleich

Task Thread

Besitzer von Betriebsmitteln Kann auszliger Prozessor selbst keine Betriebsmittel besitzen verfuumlgt aber uumlber alle Betriebsmittel der Task der er angehoumlrt

Eigener Adressraum Adressraum der Task der er angehoumlrt Threads haben einen gemeinsamen Adressraum

Enthaumllt einen oder mehrere Tasks Element einer Task

Kommunikation uumlber Taskgrenzen hinaus bevorzugt uumlber Botschaften

Kommunikation zwischen den Threads bevorzugt uumlber gleiche Daten

Task wird charakterisiert uumlber einen PCB

Thread wird charakterisiert uumlber Programmzaumlhler Register Stack und Zustand

Seite 17

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Vorteile von Threadsbull Kontextwechsel zwischen Threads effizienter als zwischen Prozessen

ndash kein Wechsel des Adressraumsndash kein automatisches Schedulingndash kein Retten und Restaurieren des Kontextes (nur Programmzaumlhler und Register)

bull Pro Zeiteinheit sind viel mehr Threadwechsel als Prozesswechsel moumlglich deshalb auch bdquoleichtgewichtigeldquo Prozesse

bull Einfachere Programmierung (gegenuumlber Tasks) wenn mehrere gleichzeitige Aktivitaumlten von denen einige von Zeit zu Zeit blockieren modelliert werden muumlssen

bull Bessere Performance bei Erzeugung und Zerstoumlrung da keine Ressourcen mit Threads verbunden sind

bull Bessere Performance bei Mischung von CPU- mit IO-intensiven Aufgaben (kein Vorteil bei reiner CPU-Nutzung

bull ABER Da die Schutzfunktion der getrennten Adressraumlume fehlt werden Synchronisationsmechanismen benoumltigt

Seite 18

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselbull Zur Erinnerung

ndash Auf einem Rechner laufen mehrere Prozessendash Es gibt meist nur eine CPUndash Das heiszligt die Prozesse muumlssen sich in der Nutzung der CPU abwechselnndash Das Betriebssystem entscheidet welcher Prozess als naumlchstes die CPU benutzen

darfbull Komponenten des Scheduling

ndash Prozesswechselkostenndash Warteschlangenmodellendash Scheduling-Verfahren

Seite 19

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselkostenbull Ein Prozesswechsel zwischen 2 Prozessen A und B schlieszligt genau genommen drei

weitere mit einndash Prozess A Unterbrechungsbearbeitung (UB)ndash UB Betriebssystem (BS)ndash BS Prozess Bndash Prozess B BS

ndash BS Prozess A

BS

Unterbr

Prozess A

Prozess B

1 KW (Kontextwechsel)

2 KW

3 KW 4 KW

5 KW

Prozess A ist verdraumlngt

bull Beim Prozesswechsel muss der Kontext des Prozesses im PCB gesichert werden dh beim 1 PW save state into PCBA und reload state from PCBB

bull Prozesswechsel sind relativ teuer (zB 122 μs auf Sun Sparc 20) 2 Prozesswechsel1 Prozesswechsel

(PW)

Seite 20

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodellebull Prozesse werden intern in Warteschlangen gehalten wenn ihnen die angeforderten

Betriebsmittel (zB die CPU) nicht zur Verfuumlgung stehen oder die erwarteten Ereignisse (zB Beendigung eines Prozesses) noch nicht eingetreten sind

bull Die Auswahlstrategien der Warteschlangen haben wesentlichen Einfluss auf das Systemverhalten

bull Prozesse migrieren aus Sicht des Betriebssystems zwischen den verschiedenen Warteschlangen

ndash Job queue (Prozessliste) Menge aller Prozesse im Systemndash Ready queue (Bereitliste CPU-Warteschlange) Menge der Prozesse die im

Hauptspeicher geladen und bereit zur Ausfuumlhrung sindndash Device queues (Warteschlange fuumlr jedes Geraumlt) Menge der Prozesse die auf ein

IO-Geraumlt warten

Seite 21

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Prozesse migrieren zwischen den Warteschlangen

Seite 22

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Beispiel

Seite 23

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Seite 24

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Ankunftszeit Task wird in Taskliste aufgenommen

Anforderungszeit Ereignis tritt ein Task wird ablaufwilligStartzeit Task erhaumllt

erstmalig die CPU zugeteilt

Beendigungszeit Task hat Aufgabe erledigt und ruht wieder

Deadline Zeit zu der die Task spaumltestens beendet sein muss

Ausfuumlhrungszeit Rechenzeit der Task (ohne Wartezeiten)

Periode Zeitdifferenz zwischen aufeinander folgenden Anforderungen

Spielraum Restzeit zwischen Beendigung und Deadline

Reaktionszeit Zeit zwischen Anfor-derung und Start der Ausfuumlhrung

Seite 25

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

ai Ankunftszeit (Arrival Time) Zeitpunkt an dem eine Task dem Betriebssystem bekannt gemacht wird die Taskverwaltung nimmt die Task in die Taskliste und setzt sie in den Zustand ruhend

ri Anforderungszeit (Request Time) Die Task bewirbt sich bei der Taskverwaltung um den Prozessor

si Startzeit (Start Time) die Task erhaumllt den Prozessor zugeteilt

ci Beendigungszeit (Completion Time) Die Task hat ihre Aufgabe erledigt und kehrt in den Zustand ruhend zuruumlck

di Zeitschranke (Deadline) Zeitpunkt an dem die Taskausfuumlhrung spaumltestens beendet sein muss Die Zeitschranke kann hart fest oder weich sein

pi Periode (Period) Zeitdauer kennzeichnet die Wiederholungsrate bei periodischen Tasks sie ergibt sich aus der Zeitdifferenz zwischen zwei aufeinander folgenden Anforderungszeiten einer Task

ei Ausfuumlhrungszeit (Execution Time) Zeitdauer die eine Task zur Ausfuumlhrung ihrer Aufgabe benoumltigt wenn sie sich im Zustand laufend befindet Eine Variante ist die maximale Ausfuumlhrungszeit (worst case execution time = WCET) eine obere Schranke der Ausfuumlhrungszeit die in keinem Fall uumlberschritten werden darf

li Spielraum (Laxity) verbleibende Restzeit zwischen Beendigungszeit und Zeitschranke

ji Reaktionszeit (Reaction Time Release Jitter) Zeitraum kennzeichnet die Verzoumlgerung zwischen Anforderung und dem Start der Ausfuumlhrung

Seite 26

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Uumlbungsfragen (Vorl Uni Stuttgart)

1048709 Eine Task im Zustand ldquorunnablerdquo wird momentan ausgefuumlhrt

1048709 Ein Task-Zustand kann direkt von ldquorunningrdquo zu ldquodormantrdquo wechseln

1048709 Eine Task im Zustand ldquosuspendedrdquo kann direkt in den Zustand ldquorunningrdquo wechseln

1048709 Eine Task im Zustand ldquodormantrdquo ist nicht bereit da Zeit- oder andere Bedingungen nicht

erfuumlllt sind

1048709 Eine Task im Zustand ldquosuspendedrdquo wartet auf das Auftreten eines Events

Seite 2

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Task = Rechenprozess bull Ein Rechenprozess ist ein von einem Echtzeit-Betriebssystem gesteuerter Vorgang der

Abarbeitung eines sequenziellen Programmsbull Rechenprozess beginnt mit Eintrag in eine Liste des Echtzeit-Betriebssystems und

endet mit dem Loumlschen aus dieser Listebull Rechenprozess existiert nicht nur waumlhrend der Ausfuumlhrung der Befehle sondern auch

waumlhrend geplanter oder erzwungener Wartezeitenbull Rechenprozess benoumltigt BetriebsmittelRessourcen (CPU-Zeit Speicherplatz Zugriff

auf EA-Geraumlte) und ist selbst ein Betriebsmittel das vom Betriebssystem (BS) verwaltet wird (Erzeugung Terminierung Scheduling )

bull Ein Prozessor fuumlhrt in jeder Zeiteinheit maximal einen Rechenprozess ausbull Laufen mehrere Prozesse auf einem Rechner finden Prozesswechsel statt Das

Betriebssystem entscheidet welcher Prozess zu welchem Zeitpunkt ausgefuumlhrt wirdbull Rechenprozesse sind gegeneinander abgeschottet ndash jeder besitzt (virtuell) seine

eigenen Betriebsmittel wie etwa den Adressraum Das BS sorgt fuumlr diese Abschottung

Seite 3

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Eigenschaften von Rechenprozessen

Ein Rechenprozess wird durch folgende Eigenschaften beschriebenbull Eine Folge von Maschinenbefehlen die durch das ausgefuumlhrte Programm (program

code text section) festgelegt sindbull Der aktuelle Zustand der Bearbeitung ist durch den Programmzaumlhler und die

Registerinhalte des Prozessors beschrieben (internal state)bull Der Inhalt des Stapelspeichers auf dem temporaumlre Variablen und Parameter fuumlr

Funktionsaufrufe verwaltet werden (stack)bull Der Inhalt des Speichers in dem die globale Daten des Prozesses gehalten werden

(data section)bull Beziehungen zu anderen Betriebsmitteln wie zB geoumlffnete Dateien (external state)

Seite 4

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesskontrollblock (PCB)bull Ein Prozess wird im Betriebssystem durch einen Prozesskontrollblock

(Prozessleitblock) repraumlsentiert in dem alle Informationen zu einem laufenden Prozess verwaltet werden

bull Beispiel fuumlr Informationen in einem PCB

Seite 5

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Multitasking bezeichnet die Faumlhigkeit eines Betriebssystems mehrere Aufgaben (Tasks) nebenlaumlufig auszufuumlhren Dabei werden die verschiedenen Prozesse in so kurzen Abstaumlnden immer abwechselnd aktiviert dass der Eindruck der Gleichzeitigkeit entsteht

bull Optimiert die Prozessor-Auslastung und verringert die Prozessor-Wartezeitbull Prozess ist ein bdquoProgramm in Ausfuumlhrungldquo

ndash Speicherabbild eines gestarteten Programms mit den vom Betriebssystem benoumltigten Systemdatenndash alle Prozesse laufen isoliert voneinander ab so dass die Prozesszustaumlnde vor der Unterbrechung gespeichert

werden muumlssenbull Voraussetzung

ndash Ein Timer-Interrupt wird in regelmaumlszligigen Abstaumlnden an die CPU geschicktndash Die zugehoumlrige Interrupt-Service-Routine loumlst den Scheduler (Prozessverwalter) aus

bull Kooperatives Multitasking (DOS Windows 31)ndash Scheduler uumlberlaumlsst Prozessen die Zuteilung von CPU Zeitndash Vorteil geringer Verwaltungsaufwand noumltig Nachteil fehlerhafter Prozess blockiert alle anderen

bull Praumlemptives Multitasking (Windows NT)ndash Scheduler verwaltet Liste aller aktiven Prozesse Reihenfolge entscheidet uumlber Dringlichkeit Aufbau der Listen

nach verschiedenen Prinzipienndash Unterbrechungen jederzeit moumlglich

Seite 6

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Kooperatives Multitasking

bull Jeder Prozess gibt seinen Status freiwillig an naumlchsten Prozess weiterbull Wenn Prozess 1 fertig ist gibt er dies an Prozess 2 weiter und

wechselt in den Status rechenbereit waumlhrend der Prozess 2 von rechenbereit auf rechnend wechselt

bull Bsp Eine Runde von Indianern die die Friedenspfeife rauchtbull Jeder Indianer in diesem Kreis stellt einen Prozess (alle rechenbereit)

dar und die Friedenspfeife stellt Rechenzeit dar

bull Rauchender Indianer entspricht dem Zustand rechnend alle anderen Indianer sind rechenbereit da sie auf die Pfeife warten

bull Das Kooperative an diesem System ist dass jeder Indianer nachdem er eine Weile geraucht hat die Pfeife freiwillig an den naumlchsten Indianer weitergibt

bull Hieraus wird auch der Nachteil des Systems sichtbar Kann oder will ein Indianer die Pfeife nicht weiterreichen kommt das System zum erliegen

bull Vorteil leicht implementierbar

Seite 7

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Praumlemptives Multitasking

bull Jedem Prozess wird bestimmtes Zeitfenster gegeben in dem er ausgefuumlhrt wird am Ende der Zeit wird der Prozess unterbrochen

bull Teil des Betriebssystems kuumlmmert sich um Wechseln zum naumlchsten Prozess und gibt dem naumlchsten auszufuumlhrenden Prozess die Kontrolle bis zum Ende des Zeitfensters

bull Bsp Haumluptling nimmt selbst die Pfeife in die Hand und reicht sie von Indianer zu Indianer weiter ohne sie aus der Hand zu geben

bull Da sich keiner zu widersprechen getraut ist der ordnungsgemaumlszlige Ablauf sichergestellt

bull Haumluptling fungiert als Interrupt der regelmaumlszligig ISR (Interrupt Service Routine sbquoPfeife weiterreichenrsquo aufruft

bull Dann gibt er dem jeweiligen Indianer der nun rauchen darf den Status running bis er ihn wieder unterbricht

bull Nachteil des Systems mehr Programmieraufwand

bull Vorteil stabil funktionierendes System

Seite 8

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Schedulerbull Bestandteil des Betriebssystemsbull sinnvolle Verteilung der CPU Zeit an aktive Prozessebull verantwortlich fuumlr die Umsetzung von Multitasking

Ziele des Schedulers (die sich jedoch im Einzelfall widersprechen koumlnnen) bull Fairness jeder Prozess soll einen gerechten Anteil an der CPU-Leistung bekommen dh

kein Prozess wird dauerhaft benachteiligtbull Effizienz CPU sollte dauerhaft belegt werdenbull Antwortzeit Antwortzeit soll fuumlr interaktive Benutzer minimal seinbull Durchsatz Anzahl der bearbeiteten Prozesse pro Zeitintervall soll maximiert werden (=

die zur Verfuumlgung stehenden Ressourcen sollen optimal ausgelastet werden)bull Verweilzeit Verweildauer von Programmen soll moumlglichst gering seinbull Terminerfuumlllung Prozesse die zu einem bestimmten Termin beendet sein

muumlssen werden so geplant dass der Termin eingehalten wird

Seite 9

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Erzeugen von Prozessen bull Prozesse werden erzeugt bei

ndash Initialisierung des Systems (einfache Systeme zB Steuerung eines Mikrowellenherds)

ndash Systemaufruf zum Erzeugen eines (Sohn-)Prozesses durch einen anderen (Vater-)Prozess

ndash Benutzeranfrage einen neuen Prozess zu erzeugenndash Initiierung einer Stapelverarbeitung (Batch-Job)

bull POSIX-Systeme benutzen hierzu den fork() Systemaufrufndash Der neu erzeugte Prozess (child) ist eine exakte Kopie des erzeugenden Prozesses (parent)

besitzt aber eine neue Prozessnummerndash Beide Prozesse fuumlhren dieselben Instruktionen nach dem fork() ausndash Der Ergebniswert des fork() Systemaufrufs ist in beiden Prozessen unterschiedlichndash Mittels des Systemaufrufs exec() koumlnnen in einem Prozess neue Programme gestartet

werden

bull Windows Systemaufruf CreateProcess()bull Da beliebige Prozesse neue Prozesse erzeugen koumlnnen entsteht eine Hierarchie

(Baum) von Prozessen die als verkettete Liste organisiert ist(POSIX = Portable Operating System Interface (Standard-Schnittstelle zw Applikation und Betriebssystem)

Seite 10

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Beenden von Prozessen bull Prozesse koumlnnen sich selbst durch den exit()-Systemaufruf beenden und damit aus

dem System entfernenbull Ein Prozess kann die von ihm erzeugten Prozesse beenden falls

ndash ein Prozess die ihm zugestandenen Betriebsmittel verbraucht hatndash ein Prozess nicht laumlnger gebraucht wird oder fallsndash der erzeugende Prozess sich beendet und es nicht gewuumlnscht oder erlaubt ist

dass die erzeugten Prozesse unabhaumlngig weiter existieren (cascading termination)bull Auf die Beendigung eines erzeugten Prozesses kann in POSIX-Systemen mit Hilfe des

wait() Systemaufrufs gewartet werdenbull Der Ergebniswert (return code) eines sich beendenden Prozesses wird an den

erzeugenden Prozess weitergeleitet

Seite 11

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

while (1) repeat forever type_prompt() display prompt on screen read_command() read input from the terminal

pid = fork() create a new

process if (pid lt 0) repeat if system call failed

perror(fork)continue

if (pid = 0) parent process

waitpid(pid ampstatus 0) wait for child

else child process execve(command params 0) execute

command

Beispiel einfacher Kommandointerpreter

als Sohnprozessals Vaterprozess

Seite 12

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Die 5 Taskzustaumlnde mit den wichtigsten Uumlbergaumlngen

dormant existent

ready bereit

running laufend terminated

beendet

suspended blockiert

Task ist der Prozessverwaltung bekannt gegeben

Task ist gestartet und alle Betriebsmittel vorhanden (eingeplant)

Betriebsmittel fehlen

Weitere Begriffe

Dormant = idle new

Existent = ruhend

Ready = runnable busy

Bereit = ablaufwillig rechenbereit

Running = executing

Laufend = ablaufend rechnend aktiv

Suspended = blocked waiting

Task ist abgearbeitet

Task ist eliminiert

Betriebsmittel vorhanden

Task ist der Prozessor zugeteilt

Task ist verdraumlngt

Seite 13

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Die 5 Taskzustaumlnde mit den wichtigsten Uumlbergaumlngen

dormant existent

ready bereit

running laufend terminated

beendet

suspended blockiert

admitted

IO or event wait

exit

Task ist eliminiert

IO or event completion

dispatch Interrupt trap

Seite 14

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Zustandsuumlbergaumlnge (Umhaumlngen in eine andere Liste) bull Es existieren drei Arten des Prozessor-Entzugs

ndash Aufgabe des Prozessors durch einen Warteaufruf Wartelistendash Verdraumlngung durch einen anderen Prozess (Praumlemption) Bereitlistendash Beendigung

bull Vom Zustand bdquoblockiertldquo geht es nicht direkt in den Zustand bdquorunningldquobull Der Uumlbergang von bdquorunningldquo nach bdquoblockiertldquo wird immer durch den Prozess selbst

initiiertbull Der Uumlbergang von bdquorunningldquo nach bdquobeendetldquo wird immer durch den Prozess selbst

initiiertbull Der Uumlbergang von bdquobereitldquo nach bdquorunningldquo und zuruumlck geschieht immer durch das

Betriebssystem

Seite 15

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Leichtgewichtsprozesse (Threads)bull Threads sind parallele Kontrollfluumlsse die nicht gegeneinander abgeschottet sind

ndash laufen innerhalb des Adressraums eines bdquoechtenldquo Rechenprozessesndash teilen sich gemeinsame Ressourcen (zB globale Variable)

bull Es gibt Threads im Betriebssystem-Kernel Scheduling durch BSbull Es gibt Threads im Usermodus des Betriebssystems Scheduling durch Anwendung

BS nur fuumlr Prozess-Scheduling verantwortlich

Kernel

Usermodus

Prozess

Thread

Seite 16

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Unterschiede zwischen Tasks und Threads

bull Aus Sicht der Betriebszustaumlnde der Zeitparameter des Schedulings und der Synchronisation sind Thread und Task gleich

Task Thread

Besitzer von Betriebsmitteln Kann auszliger Prozessor selbst keine Betriebsmittel besitzen verfuumlgt aber uumlber alle Betriebsmittel der Task der er angehoumlrt

Eigener Adressraum Adressraum der Task der er angehoumlrt Threads haben einen gemeinsamen Adressraum

Enthaumllt einen oder mehrere Tasks Element einer Task

Kommunikation uumlber Taskgrenzen hinaus bevorzugt uumlber Botschaften

Kommunikation zwischen den Threads bevorzugt uumlber gleiche Daten

Task wird charakterisiert uumlber einen PCB

Thread wird charakterisiert uumlber Programmzaumlhler Register Stack und Zustand

Seite 17

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Vorteile von Threadsbull Kontextwechsel zwischen Threads effizienter als zwischen Prozessen

ndash kein Wechsel des Adressraumsndash kein automatisches Schedulingndash kein Retten und Restaurieren des Kontextes (nur Programmzaumlhler und Register)

bull Pro Zeiteinheit sind viel mehr Threadwechsel als Prozesswechsel moumlglich deshalb auch bdquoleichtgewichtigeldquo Prozesse

bull Einfachere Programmierung (gegenuumlber Tasks) wenn mehrere gleichzeitige Aktivitaumlten von denen einige von Zeit zu Zeit blockieren modelliert werden muumlssen

bull Bessere Performance bei Erzeugung und Zerstoumlrung da keine Ressourcen mit Threads verbunden sind

bull Bessere Performance bei Mischung von CPU- mit IO-intensiven Aufgaben (kein Vorteil bei reiner CPU-Nutzung

bull ABER Da die Schutzfunktion der getrennten Adressraumlume fehlt werden Synchronisationsmechanismen benoumltigt

Seite 18

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselbull Zur Erinnerung

ndash Auf einem Rechner laufen mehrere Prozessendash Es gibt meist nur eine CPUndash Das heiszligt die Prozesse muumlssen sich in der Nutzung der CPU abwechselnndash Das Betriebssystem entscheidet welcher Prozess als naumlchstes die CPU benutzen

darfbull Komponenten des Scheduling

ndash Prozesswechselkostenndash Warteschlangenmodellendash Scheduling-Verfahren

Seite 19

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselkostenbull Ein Prozesswechsel zwischen 2 Prozessen A und B schlieszligt genau genommen drei

weitere mit einndash Prozess A Unterbrechungsbearbeitung (UB)ndash UB Betriebssystem (BS)ndash BS Prozess Bndash Prozess B BS

ndash BS Prozess A

BS

Unterbr

Prozess A

Prozess B

1 KW (Kontextwechsel)

2 KW

3 KW 4 KW

5 KW

Prozess A ist verdraumlngt

bull Beim Prozesswechsel muss der Kontext des Prozesses im PCB gesichert werden dh beim 1 PW save state into PCBA und reload state from PCBB

bull Prozesswechsel sind relativ teuer (zB 122 μs auf Sun Sparc 20) 2 Prozesswechsel1 Prozesswechsel

(PW)

Seite 20

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodellebull Prozesse werden intern in Warteschlangen gehalten wenn ihnen die angeforderten

Betriebsmittel (zB die CPU) nicht zur Verfuumlgung stehen oder die erwarteten Ereignisse (zB Beendigung eines Prozesses) noch nicht eingetreten sind

bull Die Auswahlstrategien der Warteschlangen haben wesentlichen Einfluss auf das Systemverhalten

bull Prozesse migrieren aus Sicht des Betriebssystems zwischen den verschiedenen Warteschlangen

ndash Job queue (Prozessliste) Menge aller Prozesse im Systemndash Ready queue (Bereitliste CPU-Warteschlange) Menge der Prozesse die im

Hauptspeicher geladen und bereit zur Ausfuumlhrung sindndash Device queues (Warteschlange fuumlr jedes Geraumlt) Menge der Prozesse die auf ein

IO-Geraumlt warten

Seite 21

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Prozesse migrieren zwischen den Warteschlangen

Seite 22

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Beispiel

Seite 23

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Seite 24

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Ankunftszeit Task wird in Taskliste aufgenommen

Anforderungszeit Ereignis tritt ein Task wird ablaufwilligStartzeit Task erhaumllt

erstmalig die CPU zugeteilt

Beendigungszeit Task hat Aufgabe erledigt und ruht wieder

Deadline Zeit zu der die Task spaumltestens beendet sein muss

Ausfuumlhrungszeit Rechenzeit der Task (ohne Wartezeiten)

Periode Zeitdifferenz zwischen aufeinander folgenden Anforderungen

Spielraum Restzeit zwischen Beendigung und Deadline

Reaktionszeit Zeit zwischen Anfor-derung und Start der Ausfuumlhrung

Seite 25

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

ai Ankunftszeit (Arrival Time) Zeitpunkt an dem eine Task dem Betriebssystem bekannt gemacht wird die Taskverwaltung nimmt die Task in die Taskliste und setzt sie in den Zustand ruhend

ri Anforderungszeit (Request Time) Die Task bewirbt sich bei der Taskverwaltung um den Prozessor

si Startzeit (Start Time) die Task erhaumllt den Prozessor zugeteilt

ci Beendigungszeit (Completion Time) Die Task hat ihre Aufgabe erledigt und kehrt in den Zustand ruhend zuruumlck

di Zeitschranke (Deadline) Zeitpunkt an dem die Taskausfuumlhrung spaumltestens beendet sein muss Die Zeitschranke kann hart fest oder weich sein

pi Periode (Period) Zeitdauer kennzeichnet die Wiederholungsrate bei periodischen Tasks sie ergibt sich aus der Zeitdifferenz zwischen zwei aufeinander folgenden Anforderungszeiten einer Task

ei Ausfuumlhrungszeit (Execution Time) Zeitdauer die eine Task zur Ausfuumlhrung ihrer Aufgabe benoumltigt wenn sie sich im Zustand laufend befindet Eine Variante ist die maximale Ausfuumlhrungszeit (worst case execution time = WCET) eine obere Schranke der Ausfuumlhrungszeit die in keinem Fall uumlberschritten werden darf

li Spielraum (Laxity) verbleibende Restzeit zwischen Beendigungszeit und Zeitschranke

ji Reaktionszeit (Reaction Time Release Jitter) Zeitraum kennzeichnet die Verzoumlgerung zwischen Anforderung und dem Start der Ausfuumlhrung

Seite 26

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Uumlbungsfragen (Vorl Uni Stuttgart)

1048709 Eine Task im Zustand ldquorunnablerdquo wird momentan ausgefuumlhrt

1048709 Ein Task-Zustand kann direkt von ldquorunningrdquo zu ldquodormantrdquo wechseln

1048709 Eine Task im Zustand ldquosuspendedrdquo kann direkt in den Zustand ldquorunningrdquo wechseln

1048709 Eine Task im Zustand ldquodormantrdquo ist nicht bereit da Zeit- oder andere Bedingungen nicht

erfuumlllt sind

1048709 Eine Task im Zustand ldquosuspendedrdquo wartet auf das Auftreten eines Events

Seite 3

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Eigenschaften von Rechenprozessen

Ein Rechenprozess wird durch folgende Eigenschaften beschriebenbull Eine Folge von Maschinenbefehlen die durch das ausgefuumlhrte Programm (program

code text section) festgelegt sindbull Der aktuelle Zustand der Bearbeitung ist durch den Programmzaumlhler und die

Registerinhalte des Prozessors beschrieben (internal state)bull Der Inhalt des Stapelspeichers auf dem temporaumlre Variablen und Parameter fuumlr

Funktionsaufrufe verwaltet werden (stack)bull Der Inhalt des Speichers in dem die globale Daten des Prozesses gehalten werden

(data section)bull Beziehungen zu anderen Betriebsmitteln wie zB geoumlffnete Dateien (external state)

Seite 4

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesskontrollblock (PCB)bull Ein Prozess wird im Betriebssystem durch einen Prozesskontrollblock

(Prozessleitblock) repraumlsentiert in dem alle Informationen zu einem laufenden Prozess verwaltet werden

bull Beispiel fuumlr Informationen in einem PCB

Seite 5

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Multitasking bezeichnet die Faumlhigkeit eines Betriebssystems mehrere Aufgaben (Tasks) nebenlaumlufig auszufuumlhren Dabei werden die verschiedenen Prozesse in so kurzen Abstaumlnden immer abwechselnd aktiviert dass der Eindruck der Gleichzeitigkeit entsteht

bull Optimiert die Prozessor-Auslastung und verringert die Prozessor-Wartezeitbull Prozess ist ein bdquoProgramm in Ausfuumlhrungldquo

ndash Speicherabbild eines gestarteten Programms mit den vom Betriebssystem benoumltigten Systemdatenndash alle Prozesse laufen isoliert voneinander ab so dass die Prozesszustaumlnde vor der Unterbrechung gespeichert

werden muumlssenbull Voraussetzung

ndash Ein Timer-Interrupt wird in regelmaumlszligigen Abstaumlnden an die CPU geschicktndash Die zugehoumlrige Interrupt-Service-Routine loumlst den Scheduler (Prozessverwalter) aus

bull Kooperatives Multitasking (DOS Windows 31)ndash Scheduler uumlberlaumlsst Prozessen die Zuteilung von CPU Zeitndash Vorteil geringer Verwaltungsaufwand noumltig Nachteil fehlerhafter Prozess blockiert alle anderen

bull Praumlemptives Multitasking (Windows NT)ndash Scheduler verwaltet Liste aller aktiven Prozesse Reihenfolge entscheidet uumlber Dringlichkeit Aufbau der Listen

nach verschiedenen Prinzipienndash Unterbrechungen jederzeit moumlglich

Seite 6

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Kooperatives Multitasking

bull Jeder Prozess gibt seinen Status freiwillig an naumlchsten Prozess weiterbull Wenn Prozess 1 fertig ist gibt er dies an Prozess 2 weiter und

wechselt in den Status rechenbereit waumlhrend der Prozess 2 von rechenbereit auf rechnend wechselt

bull Bsp Eine Runde von Indianern die die Friedenspfeife rauchtbull Jeder Indianer in diesem Kreis stellt einen Prozess (alle rechenbereit)

dar und die Friedenspfeife stellt Rechenzeit dar

bull Rauchender Indianer entspricht dem Zustand rechnend alle anderen Indianer sind rechenbereit da sie auf die Pfeife warten

bull Das Kooperative an diesem System ist dass jeder Indianer nachdem er eine Weile geraucht hat die Pfeife freiwillig an den naumlchsten Indianer weitergibt

bull Hieraus wird auch der Nachteil des Systems sichtbar Kann oder will ein Indianer die Pfeife nicht weiterreichen kommt das System zum erliegen

bull Vorteil leicht implementierbar

Seite 7

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Praumlemptives Multitasking

bull Jedem Prozess wird bestimmtes Zeitfenster gegeben in dem er ausgefuumlhrt wird am Ende der Zeit wird der Prozess unterbrochen

bull Teil des Betriebssystems kuumlmmert sich um Wechseln zum naumlchsten Prozess und gibt dem naumlchsten auszufuumlhrenden Prozess die Kontrolle bis zum Ende des Zeitfensters

bull Bsp Haumluptling nimmt selbst die Pfeife in die Hand und reicht sie von Indianer zu Indianer weiter ohne sie aus der Hand zu geben

bull Da sich keiner zu widersprechen getraut ist der ordnungsgemaumlszlige Ablauf sichergestellt

bull Haumluptling fungiert als Interrupt der regelmaumlszligig ISR (Interrupt Service Routine sbquoPfeife weiterreichenrsquo aufruft

bull Dann gibt er dem jeweiligen Indianer der nun rauchen darf den Status running bis er ihn wieder unterbricht

bull Nachteil des Systems mehr Programmieraufwand

bull Vorteil stabil funktionierendes System

Seite 8

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Schedulerbull Bestandteil des Betriebssystemsbull sinnvolle Verteilung der CPU Zeit an aktive Prozessebull verantwortlich fuumlr die Umsetzung von Multitasking

Ziele des Schedulers (die sich jedoch im Einzelfall widersprechen koumlnnen) bull Fairness jeder Prozess soll einen gerechten Anteil an der CPU-Leistung bekommen dh

kein Prozess wird dauerhaft benachteiligtbull Effizienz CPU sollte dauerhaft belegt werdenbull Antwortzeit Antwortzeit soll fuumlr interaktive Benutzer minimal seinbull Durchsatz Anzahl der bearbeiteten Prozesse pro Zeitintervall soll maximiert werden (=

die zur Verfuumlgung stehenden Ressourcen sollen optimal ausgelastet werden)bull Verweilzeit Verweildauer von Programmen soll moumlglichst gering seinbull Terminerfuumlllung Prozesse die zu einem bestimmten Termin beendet sein

muumlssen werden so geplant dass der Termin eingehalten wird

Seite 9

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Erzeugen von Prozessen bull Prozesse werden erzeugt bei

ndash Initialisierung des Systems (einfache Systeme zB Steuerung eines Mikrowellenherds)

ndash Systemaufruf zum Erzeugen eines (Sohn-)Prozesses durch einen anderen (Vater-)Prozess

ndash Benutzeranfrage einen neuen Prozess zu erzeugenndash Initiierung einer Stapelverarbeitung (Batch-Job)

bull POSIX-Systeme benutzen hierzu den fork() Systemaufrufndash Der neu erzeugte Prozess (child) ist eine exakte Kopie des erzeugenden Prozesses (parent)

besitzt aber eine neue Prozessnummerndash Beide Prozesse fuumlhren dieselben Instruktionen nach dem fork() ausndash Der Ergebniswert des fork() Systemaufrufs ist in beiden Prozessen unterschiedlichndash Mittels des Systemaufrufs exec() koumlnnen in einem Prozess neue Programme gestartet

werden

bull Windows Systemaufruf CreateProcess()bull Da beliebige Prozesse neue Prozesse erzeugen koumlnnen entsteht eine Hierarchie

(Baum) von Prozessen die als verkettete Liste organisiert ist(POSIX = Portable Operating System Interface (Standard-Schnittstelle zw Applikation und Betriebssystem)

Seite 10

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Beenden von Prozessen bull Prozesse koumlnnen sich selbst durch den exit()-Systemaufruf beenden und damit aus

dem System entfernenbull Ein Prozess kann die von ihm erzeugten Prozesse beenden falls

ndash ein Prozess die ihm zugestandenen Betriebsmittel verbraucht hatndash ein Prozess nicht laumlnger gebraucht wird oder fallsndash der erzeugende Prozess sich beendet und es nicht gewuumlnscht oder erlaubt ist

dass die erzeugten Prozesse unabhaumlngig weiter existieren (cascading termination)bull Auf die Beendigung eines erzeugten Prozesses kann in POSIX-Systemen mit Hilfe des

wait() Systemaufrufs gewartet werdenbull Der Ergebniswert (return code) eines sich beendenden Prozesses wird an den

erzeugenden Prozess weitergeleitet

Seite 11

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

while (1) repeat forever type_prompt() display prompt on screen read_command() read input from the terminal

pid = fork() create a new

process if (pid lt 0) repeat if system call failed

perror(fork)continue

if (pid = 0) parent process

waitpid(pid ampstatus 0) wait for child

else child process execve(command params 0) execute

command

Beispiel einfacher Kommandointerpreter

als Sohnprozessals Vaterprozess

Seite 12

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Die 5 Taskzustaumlnde mit den wichtigsten Uumlbergaumlngen

dormant existent

ready bereit

running laufend terminated

beendet

suspended blockiert

Task ist der Prozessverwaltung bekannt gegeben

Task ist gestartet und alle Betriebsmittel vorhanden (eingeplant)

Betriebsmittel fehlen

Weitere Begriffe

Dormant = idle new

Existent = ruhend

Ready = runnable busy

Bereit = ablaufwillig rechenbereit

Running = executing

Laufend = ablaufend rechnend aktiv

Suspended = blocked waiting

Task ist abgearbeitet

Task ist eliminiert

Betriebsmittel vorhanden

Task ist der Prozessor zugeteilt

Task ist verdraumlngt

Seite 13

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Die 5 Taskzustaumlnde mit den wichtigsten Uumlbergaumlngen

dormant existent

ready bereit

running laufend terminated

beendet

suspended blockiert

admitted

IO or event wait

exit

Task ist eliminiert

IO or event completion

dispatch Interrupt trap

Seite 14

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Zustandsuumlbergaumlnge (Umhaumlngen in eine andere Liste) bull Es existieren drei Arten des Prozessor-Entzugs

ndash Aufgabe des Prozessors durch einen Warteaufruf Wartelistendash Verdraumlngung durch einen anderen Prozess (Praumlemption) Bereitlistendash Beendigung

bull Vom Zustand bdquoblockiertldquo geht es nicht direkt in den Zustand bdquorunningldquobull Der Uumlbergang von bdquorunningldquo nach bdquoblockiertldquo wird immer durch den Prozess selbst

initiiertbull Der Uumlbergang von bdquorunningldquo nach bdquobeendetldquo wird immer durch den Prozess selbst

initiiertbull Der Uumlbergang von bdquobereitldquo nach bdquorunningldquo und zuruumlck geschieht immer durch das

Betriebssystem

Seite 15

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Leichtgewichtsprozesse (Threads)bull Threads sind parallele Kontrollfluumlsse die nicht gegeneinander abgeschottet sind

ndash laufen innerhalb des Adressraums eines bdquoechtenldquo Rechenprozessesndash teilen sich gemeinsame Ressourcen (zB globale Variable)

bull Es gibt Threads im Betriebssystem-Kernel Scheduling durch BSbull Es gibt Threads im Usermodus des Betriebssystems Scheduling durch Anwendung

BS nur fuumlr Prozess-Scheduling verantwortlich

Kernel

Usermodus

Prozess

Thread

Seite 16

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Unterschiede zwischen Tasks und Threads

bull Aus Sicht der Betriebszustaumlnde der Zeitparameter des Schedulings und der Synchronisation sind Thread und Task gleich

Task Thread

Besitzer von Betriebsmitteln Kann auszliger Prozessor selbst keine Betriebsmittel besitzen verfuumlgt aber uumlber alle Betriebsmittel der Task der er angehoumlrt

Eigener Adressraum Adressraum der Task der er angehoumlrt Threads haben einen gemeinsamen Adressraum

Enthaumllt einen oder mehrere Tasks Element einer Task

Kommunikation uumlber Taskgrenzen hinaus bevorzugt uumlber Botschaften

Kommunikation zwischen den Threads bevorzugt uumlber gleiche Daten

Task wird charakterisiert uumlber einen PCB

Thread wird charakterisiert uumlber Programmzaumlhler Register Stack und Zustand

Seite 17

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Vorteile von Threadsbull Kontextwechsel zwischen Threads effizienter als zwischen Prozessen

ndash kein Wechsel des Adressraumsndash kein automatisches Schedulingndash kein Retten und Restaurieren des Kontextes (nur Programmzaumlhler und Register)

bull Pro Zeiteinheit sind viel mehr Threadwechsel als Prozesswechsel moumlglich deshalb auch bdquoleichtgewichtigeldquo Prozesse

bull Einfachere Programmierung (gegenuumlber Tasks) wenn mehrere gleichzeitige Aktivitaumlten von denen einige von Zeit zu Zeit blockieren modelliert werden muumlssen

bull Bessere Performance bei Erzeugung und Zerstoumlrung da keine Ressourcen mit Threads verbunden sind

bull Bessere Performance bei Mischung von CPU- mit IO-intensiven Aufgaben (kein Vorteil bei reiner CPU-Nutzung

bull ABER Da die Schutzfunktion der getrennten Adressraumlume fehlt werden Synchronisationsmechanismen benoumltigt

Seite 18

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselbull Zur Erinnerung

ndash Auf einem Rechner laufen mehrere Prozessendash Es gibt meist nur eine CPUndash Das heiszligt die Prozesse muumlssen sich in der Nutzung der CPU abwechselnndash Das Betriebssystem entscheidet welcher Prozess als naumlchstes die CPU benutzen

darfbull Komponenten des Scheduling

ndash Prozesswechselkostenndash Warteschlangenmodellendash Scheduling-Verfahren

Seite 19

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselkostenbull Ein Prozesswechsel zwischen 2 Prozessen A und B schlieszligt genau genommen drei

weitere mit einndash Prozess A Unterbrechungsbearbeitung (UB)ndash UB Betriebssystem (BS)ndash BS Prozess Bndash Prozess B BS

ndash BS Prozess A

BS

Unterbr

Prozess A

Prozess B

1 KW (Kontextwechsel)

2 KW

3 KW 4 KW

5 KW

Prozess A ist verdraumlngt

bull Beim Prozesswechsel muss der Kontext des Prozesses im PCB gesichert werden dh beim 1 PW save state into PCBA und reload state from PCBB

bull Prozesswechsel sind relativ teuer (zB 122 μs auf Sun Sparc 20) 2 Prozesswechsel1 Prozesswechsel

(PW)

Seite 20

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodellebull Prozesse werden intern in Warteschlangen gehalten wenn ihnen die angeforderten

Betriebsmittel (zB die CPU) nicht zur Verfuumlgung stehen oder die erwarteten Ereignisse (zB Beendigung eines Prozesses) noch nicht eingetreten sind

bull Die Auswahlstrategien der Warteschlangen haben wesentlichen Einfluss auf das Systemverhalten

bull Prozesse migrieren aus Sicht des Betriebssystems zwischen den verschiedenen Warteschlangen

ndash Job queue (Prozessliste) Menge aller Prozesse im Systemndash Ready queue (Bereitliste CPU-Warteschlange) Menge der Prozesse die im

Hauptspeicher geladen und bereit zur Ausfuumlhrung sindndash Device queues (Warteschlange fuumlr jedes Geraumlt) Menge der Prozesse die auf ein

IO-Geraumlt warten

Seite 21

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Prozesse migrieren zwischen den Warteschlangen

Seite 22

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Beispiel

Seite 23

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Seite 24

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Ankunftszeit Task wird in Taskliste aufgenommen

Anforderungszeit Ereignis tritt ein Task wird ablaufwilligStartzeit Task erhaumllt

erstmalig die CPU zugeteilt

Beendigungszeit Task hat Aufgabe erledigt und ruht wieder

Deadline Zeit zu der die Task spaumltestens beendet sein muss

Ausfuumlhrungszeit Rechenzeit der Task (ohne Wartezeiten)

Periode Zeitdifferenz zwischen aufeinander folgenden Anforderungen

Spielraum Restzeit zwischen Beendigung und Deadline

Reaktionszeit Zeit zwischen Anfor-derung und Start der Ausfuumlhrung

Seite 25

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

ai Ankunftszeit (Arrival Time) Zeitpunkt an dem eine Task dem Betriebssystem bekannt gemacht wird die Taskverwaltung nimmt die Task in die Taskliste und setzt sie in den Zustand ruhend

ri Anforderungszeit (Request Time) Die Task bewirbt sich bei der Taskverwaltung um den Prozessor

si Startzeit (Start Time) die Task erhaumllt den Prozessor zugeteilt

ci Beendigungszeit (Completion Time) Die Task hat ihre Aufgabe erledigt und kehrt in den Zustand ruhend zuruumlck

di Zeitschranke (Deadline) Zeitpunkt an dem die Taskausfuumlhrung spaumltestens beendet sein muss Die Zeitschranke kann hart fest oder weich sein

pi Periode (Period) Zeitdauer kennzeichnet die Wiederholungsrate bei periodischen Tasks sie ergibt sich aus der Zeitdifferenz zwischen zwei aufeinander folgenden Anforderungszeiten einer Task

ei Ausfuumlhrungszeit (Execution Time) Zeitdauer die eine Task zur Ausfuumlhrung ihrer Aufgabe benoumltigt wenn sie sich im Zustand laufend befindet Eine Variante ist die maximale Ausfuumlhrungszeit (worst case execution time = WCET) eine obere Schranke der Ausfuumlhrungszeit die in keinem Fall uumlberschritten werden darf

li Spielraum (Laxity) verbleibende Restzeit zwischen Beendigungszeit und Zeitschranke

ji Reaktionszeit (Reaction Time Release Jitter) Zeitraum kennzeichnet die Verzoumlgerung zwischen Anforderung und dem Start der Ausfuumlhrung

Seite 26

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Uumlbungsfragen (Vorl Uni Stuttgart)

1048709 Eine Task im Zustand ldquorunnablerdquo wird momentan ausgefuumlhrt

1048709 Ein Task-Zustand kann direkt von ldquorunningrdquo zu ldquodormantrdquo wechseln

1048709 Eine Task im Zustand ldquosuspendedrdquo kann direkt in den Zustand ldquorunningrdquo wechseln

1048709 Eine Task im Zustand ldquodormantrdquo ist nicht bereit da Zeit- oder andere Bedingungen nicht

erfuumlllt sind

1048709 Eine Task im Zustand ldquosuspendedrdquo wartet auf das Auftreten eines Events

Seite 4

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesskontrollblock (PCB)bull Ein Prozess wird im Betriebssystem durch einen Prozesskontrollblock

(Prozessleitblock) repraumlsentiert in dem alle Informationen zu einem laufenden Prozess verwaltet werden

bull Beispiel fuumlr Informationen in einem PCB

Seite 5

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Multitasking bezeichnet die Faumlhigkeit eines Betriebssystems mehrere Aufgaben (Tasks) nebenlaumlufig auszufuumlhren Dabei werden die verschiedenen Prozesse in so kurzen Abstaumlnden immer abwechselnd aktiviert dass der Eindruck der Gleichzeitigkeit entsteht

bull Optimiert die Prozessor-Auslastung und verringert die Prozessor-Wartezeitbull Prozess ist ein bdquoProgramm in Ausfuumlhrungldquo

ndash Speicherabbild eines gestarteten Programms mit den vom Betriebssystem benoumltigten Systemdatenndash alle Prozesse laufen isoliert voneinander ab so dass die Prozesszustaumlnde vor der Unterbrechung gespeichert

werden muumlssenbull Voraussetzung

ndash Ein Timer-Interrupt wird in regelmaumlszligigen Abstaumlnden an die CPU geschicktndash Die zugehoumlrige Interrupt-Service-Routine loumlst den Scheduler (Prozessverwalter) aus

bull Kooperatives Multitasking (DOS Windows 31)ndash Scheduler uumlberlaumlsst Prozessen die Zuteilung von CPU Zeitndash Vorteil geringer Verwaltungsaufwand noumltig Nachteil fehlerhafter Prozess blockiert alle anderen

bull Praumlemptives Multitasking (Windows NT)ndash Scheduler verwaltet Liste aller aktiven Prozesse Reihenfolge entscheidet uumlber Dringlichkeit Aufbau der Listen

nach verschiedenen Prinzipienndash Unterbrechungen jederzeit moumlglich

Seite 6

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Kooperatives Multitasking

bull Jeder Prozess gibt seinen Status freiwillig an naumlchsten Prozess weiterbull Wenn Prozess 1 fertig ist gibt er dies an Prozess 2 weiter und

wechselt in den Status rechenbereit waumlhrend der Prozess 2 von rechenbereit auf rechnend wechselt

bull Bsp Eine Runde von Indianern die die Friedenspfeife rauchtbull Jeder Indianer in diesem Kreis stellt einen Prozess (alle rechenbereit)

dar und die Friedenspfeife stellt Rechenzeit dar

bull Rauchender Indianer entspricht dem Zustand rechnend alle anderen Indianer sind rechenbereit da sie auf die Pfeife warten

bull Das Kooperative an diesem System ist dass jeder Indianer nachdem er eine Weile geraucht hat die Pfeife freiwillig an den naumlchsten Indianer weitergibt

bull Hieraus wird auch der Nachteil des Systems sichtbar Kann oder will ein Indianer die Pfeife nicht weiterreichen kommt das System zum erliegen

bull Vorteil leicht implementierbar

Seite 7

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Praumlemptives Multitasking

bull Jedem Prozess wird bestimmtes Zeitfenster gegeben in dem er ausgefuumlhrt wird am Ende der Zeit wird der Prozess unterbrochen

bull Teil des Betriebssystems kuumlmmert sich um Wechseln zum naumlchsten Prozess und gibt dem naumlchsten auszufuumlhrenden Prozess die Kontrolle bis zum Ende des Zeitfensters

bull Bsp Haumluptling nimmt selbst die Pfeife in die Hand und reicht sie von Indianer zu Indianer weiter ohne sie aus der Hand zu geben

bull Da sich keiner zu widersprechen getraut ist der ordnungsgemaumlszlige Ablauf sichergestellt

bull Haumluptling fungiert als Interrupt der regelmaumlszligig ISR (Interrupt Service Routine sbquoPfeife weiterreichenrsquo aufruft

bull Dann gibt er dem jeweiligen Indianer der nun rauchen darf den Status running bis er ihn wieder unterbricht

bull Nachteil des Systems mehr Programmieraufwand

bull Vorteil stabil funktionierendes System

Seite 8

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Schedulerbull Bestandteil des Betriebssystemsbull sinnvolle Verteilung der CPU Zeit an aktive Prozessebull verantwortlich fuumlr die Umsetzung von Multitasking

Ziele des Schedulers (die sich jedoch im Einzelfall widersprechen koumlnnen) bull Fairness jeder Prozess soll einen gerechten Anteil an der CPU-Leistung bekommen dh

kein Prozess wird dauerhaft benachteiligtbull Effizienz CPU sollte dauerhaft belegt werdenbull Antwortzeit Antwortzeit soll fuumlr interaktive Benutzer minimal seinbull Durchsatz Anzahl der bearbeiteten Prozesse pro Zeitintervall soll maximiert werden (=

die zur Verfuumlgung stehenden Ressourcen sollen optimal ausgelastet werden)bull Verweilzeit Verweildauer von Programmen soll moumlglichst gering seinbull Terminerfuumlllung Prozesse die zu einem bestimmten Termin beendet sein

muumlssen werden so geplant dass der Termin eingehalten wird

Seite 9

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Erzeugen von Prozessen bull Prozesse werden erzeugt bei

ndash Initialisierung des Systems (einfache Systeme zB Steuerung eines Mikrowellenherds)

ndash Systemaufruf zum Erzeugen eines (Sohn-)Prozesses durch einen anderen (Vater-)Prozess

ndash Benutzeranfrage einen neuen Prozess zu erzeugenndash Initiierung einer Stapelverarbeitung (Batch-Job)

bull POSIX-Systeme benutzen hierzu den fork() Systemaufrufndash Der neu erzeugte Prozess (child) ist eine exakte Kopie des erzeugenden Prozesses (parent)

besitzt aber eine neue Prozessnummerndash Beide Prozesse fuumlhren dieselben Instruktionen nach dem fork() ausndash Der Ergebniswert des fork() Systemaufrufs ist in beiden Prozessen unterschiedlichndash Mittels des Systemaufrufs exec() koumlnnen in einem Prozess neue Programme gestartet

werden

bull Windows Systemaufruf CreateProcess()bull Da beliebige Prozesse neue Prozesse erzeugen koumlnnen entsteht eine Hierarchie

(Baum) von Prozessen die als verkettete Liste organisiert ist(POSIX = Portable Operating System Interface (Standard-Schnittstelle zw Applikation und Betriebssystem)

Seite 10

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Beenden von Prozessen bull Prozesse koumlnnen sich selbst durch den exit()-Systemaufruf beenden und damit aus

dem System entfernenbull Ein Prozess kann die von ihm erzeugten Prozesse beenden falls

ndash ein Prozess die ihm zugestandenen Betriebsmittel verbraucht hatndash ein Prozess nicht laumlnger gebraucht wird oder fallsndash der erzeugende Prozess sich beendet und es nicht gewuumlnscht oder erlaubt ist

dass die erzeugten Prozesse unabhaumlngig weiter existieren (cascading termination)bull Auf die Beendigung eines erzeugten Prozesses kann in POSIX-Systemen mit Hilfe des

wait() Systemaufrufs gewartet werdenbull Der Ergebniswert (return code) eines sich beendenden Prozesses wird an den

erzeugenden Prozess weitergeleitet

Seite 11

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

while (1) repeat forever type_prompt() display prompt on screen read_command() read input from the terminal

pid = fork() create a new

process if (pid lt 0) repeat if system call failed

perror(fork)continue

if (pid = 0) parent process

waitpid(pid ampstatus 0) wait for child

else child process execve(command params 0) execute

command

Beispiel einfacher Kommandointerpreter

als Sohnprozessals Vaterprozess

Seite 12

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Die 5 Taskzustaumlnde mit den wichtigsten Uumlbergaumlngen

dormant existent

ready bereit

running laufend terminated

beendet

suspended blockiert

Task ist der Prozessverwaltung bekannt gegeben

Task ist gestartet und alle Betriebsmittel vorhanden (eingeplant)

Betriebsmittel fehlen

Weitere Begriffe

Dormant = idle new

Existent = ruhend

Ready = runnable busy

Bereit = ablaufwillig rechenbereit

Running = executing

Laufend = ablaufend rechnend aktiv

Suspended = blocked waiting

Task ist abgearbeitet

Task ist eliminiert

Betriebsmittel vorhanden

Task ist der Prozessor zugeteilt

Task ist verdraumlngt

Seite 13

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Die 5 Taskzustaumlnde mit den wichtigsten Uumlbergaumlngen

dormant existent

ready bereit

running laufend terminated

beendet

suspended blockiert

admitted

IO or event wait

exit

Task ist eliminiert

IO or event completion

dispatch Interrupt trap

Seite 14

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Zustandsuumlbergaumlnge (Umhaumlngen in eine andere Liste) bull Es existieren drei Arten des Prozessor-Entzugs

ndash Aufgabe des Prozessors durch einen Warteaufruf Wartelistendash Verdraumlngung durch einen anderen Prozess (Praumlemption) Bereitlistendash Beendigung

bull Vom Zustand bdquoblockiertldquo geht es nicht direkt in den Zustand bdquorunningldquobull Der Uumlbergang von bdquorunningldquo nach bdquoblockiertldquo wird immer durch den Prozess selbst

initiiertbull Der Uumlbergang von bdquorunningldquo nach bdquobeendetldquo wird immer durch den Prozess selbst

initiiertbull Der Uumlbergang von bdquobereitldquo nach bdquorunningldquo und zuruumlck geschieht immer durch das

Betriebssystem

Seite 15

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Leichtgewichtsprozesse (Threads)bull Threads sind parallele Kontrollfluumlsse die nicht gegeneinander abgeschottet sind

ndash laufen innerhalb des Adressraums eines bdquoechtenldquo Rechenprozessesndash teilen sich gemeinsame Ressourcen (zB globale Variable)

bull Es gibt Threads im Betriebssystem-Kernel Scheduling durch BSbull Es gibt Threads im Usermodus des Betriebssystems Scheduling durch Anwendung

BS nur fuumlr Prozess-Scheduling verantwortlich

Kernel

Usermodus

Prozess

Thread

Seite 16

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Unterschiede zwischen Tasks und Threads

bull Aus Sicht der Betriebszustaumlnde der Zeitparameter des Schedulings und der Synchronisation sind Thread und Task gleich

Task Thread

Besitzer von Betriebsmitteln Kann auszliger Prozessor selbst keine Betriebsmittel besitzen verfuumlgt aber uumlber alle Betriebsmittel der Task der er angehoumlrt

Eigener Adressraum Adressraum der Task der er angehoumlrt Threads haben einen gemeinsamen Adressraum

Enthaumllt einen oder mehrere Tasks Element einer Task

Kommunikation uumlber Taskgrenzen hinaus bevorzugt uumlber Botschaften

Kommunikation zwischen den Threads bevorzugt uumlber gleiche Daten

Task wird charakterisiert uumlber einen PCB

Thread wird charakterisiert uumlber Programmzaumlhler Register Stack und Zustand

Seite 17

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Vorteile von Threadsbull Kontextwechsel zwischen Threads effizienter als zwischen Prozessen

ndash kein Wechsel des Adressraumsndash kein automatisches Schedulingndash kein Retten und Restaurieren des Kontextes (nur Programmzaumlhler und Register)

bull Pro Zeiteinheit sind viel mehr Threadwechsel als Prozesswechsel moumlglich deshalb auch bdquoleichtgewichtigeldquo Prozesse

bull Einfachere Programmierung (gegenuumlber Tasks) wenn mehrere gleichzeitige Aktivitaumlten von denen einige von Zeit zu Zeit blockieren modelliert werden muumlssen

bull Bessere Performance bei Erzeugung und Zerstoumlrung da keine Ressourcen mit Threads verbunden sind

bull Bessere Performance bei Mischung von CPU- mit IO-intensiven Aufgaben (kein Vorteil bei reiner CPU-Nutzung

bull ABER Da die Schutzfunktion der getrennten Adressraumlume fehlt werden Synchronisationsmechanismen benoumltigt

Seite 18

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselbull Zur Erinnerung

ndash Auf einem Rechner laufen mehrere Prozessendash Es gibt meist nur eine CPUndash Das heiszligt die Prozesse muumlssen sich in der Nutzung der CPU abwechselnndash Das Betriebssystem entscheidet welcher Prozess als naumlchstes die CPU benutzen

darfbull Komponenten des Scheduling

ndash Prozesswechselkostenndash Warteschlangenmodellendash Scheduling-Verfahren

Seite 19

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselkostenbull Ein Prozesswechsel zwischen 2 Prozessen A und B schlieszligt genau genommen drei

weitere mit einndash Prozess A Unterbrechungsbearbeitung (UB)ndash UB Betriebssystem (BS)ndash BS Prozess Bndash Prozess B BS

ndash BS Prozess A

BS

Unterbr

Prozess A

Prozess B

1 KW (Kontextwechsel)

2 KW

3 KW 4 KW

5 KW

Prozess A ist verdraumlngt

bull Beim Prozesswechsel muss der Kontext des Prozesses im PCB gesichert werden dh beim 1 PW save state into PCBA und reload state from PCBB

bull Prozesswechsel sind relativ teuer (zB 122 μs auf Sun Sparc 20) 2 Prozesswechsel1 Prozesswechsel

(PW)

Seite 20

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodellebull Prozesse werden intern in Warteschlangen gehalten wenn ihnen die angeforderten

Betriebsmittel (zB die CPU) nicht zur Verfuumlgung stehen oder die erwarteten Ereignisse (zB Beendigung eines Prozesses) noch nicht eingetreten sind

bull Die Auswahlstrategien der Warteschlangen haben wesentlichen Einfluss auf das Systemverhalten

bull Prozesse migrieren aus Sicht des Betriebssystems zwischen den verschiedenen Warteschlangen

ndash Job queue (Prozessliste) Menge aller Prozesse im Systemndash Ready queue (Bereitliste CPU-Warteschlange) Menge der Prozesse die im

Hauptspeicher geladen und bereit zur Ausfuumlhrung sindndash Device queues (Warteschlange fuumlr jedes Geraumlt) Menge der Prozesse die auf ein

IO-Geraumlt warten

Seite 21

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Prozesse migrieren zwischen den Warteschlangen

Seite 22

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Beispiel

Seite 23

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Seite 24

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Ankunftszeit Task wird in Taskliste aufgenommen

Anforderungszeit Ereignis tritt ein Task wird ablaufwilligStartzeit Task erhaumllt

erstmalig die CPU zugeteilt

Beendigungszeit Task hat Aufgabe erledigt und ruht wieder

Deadline Zeit zu der die Task spaumltestens beendet sein muss

Ausfuumlhrungszeit Rechenzeit der Task (ohne Wartezeiten)

Periode Zeitdifferenz zwischen aufeinander folgenden Anforderungen

Spielraum Restzeit zwischen Beendigung und Deadline

Reaktionszeit Zeit zwischen Anfor-derung und Start der Ausfuumlhrung

Seite 25

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

ai Ankunftszeit (Arrival Time) Zeitpunkt an dem eine Task dem Betriebssystem bekannt gemacht wird die Taskverwaltung nimmt die Task in die Taskliste und setzt sie in den Zustand ruhend

ri Anforderungszeit (Request Time) Die Task bewirbt sich bei der Taskverwaltung um den Prozessor

si Startzeit (Start Time) die Task erhaumllt den Prozessor zugeteilt

ci Beendigungszeit (Completion Time) Die Task hat ihre Aufgabe erledigt und kehrt in den Zustand ruhend zuruumlck

di Zeitschranke (Deadline) Zeitpunkt an dem die Taskausfuumlhrung spaumltestens beendet sein muss Die Zeitschranke kann hart fest oder weich sein

pi Periode (Period) Zeitdauer kennzeichnet die Wiederholungsrate bei periodischen Tasks sie ergibt sich aus der Zeitdifferenz zwischen zwei aufeinander folgenden Anforderungszeiten einer Task

ei Ausfuumlhrungszeit (Execution Time) Zeitdauer die eine Task zur Ausfuumlhrung ihrer Aufgabe benoumltigt wenn sie sich im Zustand laufend befindet Eine Variante ist die maximale Ausfuumlhrungszeit (worst case execution time = WCET) eine obere Schranke der Ausfuumlhrungszeit die in keinem Fall uumlberschritten werden darf

li Spielraum (Laxity) verbleibende Restzeit zwischen Beendigungszeit und Zeitschranke

ji Reaktionszeit (Reaction Time Release Jitter) Zeitraum kennzeichnet die Verzoumlgerung zwischen Anforderung und dem Start der Ausfuumlhrung

Seite 26

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Uumlbungsfragen (Vorl Uni Stuttgart)

1048709 Eine Task im Zustand ldquorunnablerdquo wird momentan ausgefuumlhrt

1048709 Ein Task-Zustand kann direkt von ldquorunningrdquo zu ldquodormantrdquo wechseln

1048709 Eine Task im Zustand ldquosuspendedrdquo kann direkt in den Zustand ldquorunningrdquo wechseln

1048709 Eine Task im Zustand ldquodormantrdquo ist nicht bereit da Zeit- oder andere Bedingungen nicht

erfuumlllt sind

1048709 Eine Task im Zustand ldquosuspendedrdquo wartet auf das Auftreten eines Events

Seite 5

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Multitasking bezeichnet die Faumlhigkeit eines Betriebssystems mehrere Aufgaben (Tasks) nebenlaumlufig auszufuumlhren Dabei werden die verschiedenen Prozesse in so kurzen Abstaumlnden immer abwechselnd aktiviert dass der Eindruck der Gleichzeitigkeit entsteht

bull Optimiert die Prozessor-Auslastung und verringert die Prozessor-Wartezeitbull Prozess ist ein bdquoProgramm in Ausfuumlhrungldquo

ndash Speicherabbild eines gestarteten Programms mit den vom Betriebssystem benoumltigten Systemdatenndash alle Prozesse laufen isoliert voneinander ab so dass die Prozesszustaumlnde vor der Unterbrechung gespeichert

werden muumlssenbull Voraussetzung

ndash Ein Timer-Interrupt wird in regelmaumlszligigen Abstaumlnden an die CPU geschicktndash Die zugehoumlrige Interrupt-Service-Routine loumlst den Scheduler (Prozessverwalter) aus

bull Kooperatives Multitasking (DOS Windows 31)ndash Scheduler uumlberlaumlsst Prozessen die Zuteilung von CPU Zeitndash Vorteil geringer Verwaltungsaufwand noumltig Nachteil fehlerhafter Prozess blockiert alle anderen

bull Praumlemptives Multitasking (Windows NT)ndash Scheduler verwaltet Liste aller aktiven Prozesse Reihenfolge entscheidet uumlber Dringlichkeit Aufbau der Listen

nach verschiedenen Prinzipienndash Unterbrechungen jederzeit moumlglich

Seite 6

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Kooperatives Multitasking

bull Jeder Prozess gibt seinen Status freiwillig an naumlchsten Prozess weiterbull Wenn Prozess 1 fertig ist gibt er dies an Prozess 2 weiter und

wechselt in den Status rechenbereit waumlhrend der Prozess 2 von rechenbereit auf rechnend wechselt

bull Bsp Eine Runde von Indianern die die Friedenspfeife rauchtbull Jeder Indianer in diesem Kreis stellt einen Prozess (alle rechenbereit)

dar und die Friedenspfeife stellt Rechenzeit dar

bull Rauchender Indianer entspricht dem Zustand rechnend alle anderen Indianer sind rechenbereit da sie auf die Pfeife warten

bull Das Kooperative an diesem System ist dass jeder Indianer nachdem er eine Weile geraucht hat die Pfeife freiwillig an den naumlchsten Indianer weitergibt

bull Hieraus wird auch der Nachteil des Systems sichtbar Kann oder will ein Indianer die Pfeife nicht weiterreichen kommt das System zum erliegen

bull Vorteil leicht implementierbar

Seite 7

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Praumlemptives Multitasking

bull Jedem Prozess wird bestimmtes Zeitfenster gegeben in dem er ausgefuumlhrt wird am Ende der Zeit wird der Prozess unterbrochen

bull Teil des Betriebssystems kuumlmmert sich um Wechseln zum naumlchsten Prozess und gibt dem naumlchsten auszufuumlhrenden Prozess die Kontrolle bis zum Ende des Zeitfensters

bull Bsp Haumluptling nimmt selbst die Pfeife in die Hand und reicht sie von Indianer zu Indianer weiter ohne sie aus der Hand zu geben

bull Da sich keiner zu widersprechen getraut ist der ordnungsgemaumlszlige Ablauf sichergestellt

bull Haumluptling fungiert als Interrupt der regelmaumlszligig ISR (Interrupt Service Routine sbquoPfeife weiterreichenrsquo aufruft

bull Dann gibt er dem jeweiligen Indianer der nun rauchen darf den Status running bis er ihn wieder unterbricht

bull Nachteil des Systems mehr Programmieraufwand

bull Vorteil stabil funktionierendes System

Seite 8

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Schedulerbull Bestandteil des Betriebssystemsbull sinnvolle Verteilung der CPU Zeit an aktive Prozessebull verantwortlich fuumlr die Umsetzung von Multitasking

Ziele des Schedulers (die sich jedoch im Einzelfall widersprechen koumlnnen) bull Fairness jeder Prozess soll einen gerechten Anteil an der CPU-Leistung bekommen dh

kein Prozess wird dauerhaft benachteiligtbull Effizienz CPU sollte dauerhaft belegt werdenbull Antwortzeit Antwortzeit soll fuumlr interaktive Benutzer minimal seinbull Durchsatz Anzahl der bearbeiteten Prozesse pro Zeitintervall soll maximiert werden (=

die zur Verfuumlgung stehenden Ressourcen sollen optimal ausgelastet werden)bull Verweilzeit Verweildauer von Programmen soll moumlglichst gering seinbull Terminerfuumlllung Prozesse die zu einem bestimmten Termin beendet sein

muumlssen werden so geplant dass der Termin eingehalten wird

Seite 9

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Erzeugen von Prozessen bull Prozesse werden erzeugt bei

ndash Initialisierung des Systems (einfache Systeme zB Steuerung eines Mikrowellenherds)

ndash Systemaufruf zum Erzeugen eines (Sohn-)Prozesses durch einen anderen (Vater-)Prozess

ndash Benutzeranfrage einen neuen Prozess zu erzeugenndash Initiierung einer Stapelverarbeitung (Batch-Job)

bull POSIX-Systeme benutzen hierzu den fork() Systemaufrufndash Der neu erzeugte Prozess (child) ist eine exakte Kopie des erzeugenden Prozesses (parent)

besitzt aber eine neue Prozessnummerndash Beide Prozesse fuumlhren dieselben Instruktionen nach dem fork() ausndash Der Ergebniswert des fork() Systemaufrufs ist in beiden Prozessen unterschiedlichndash Mittels des Systemaufrufs exec() koumlnnen in einem Prozess neue Programme gestartet

werden

bull Windows Systemaufruf CreateProcess()bull Da beliebige Prozesse neue Prozesse erzeugen koumlnnen entsteht eine Hierarchie

(Baum) von Prozessen die als verkettete Liste organisiert ist(POSIX = Portable Operating System Interface (Standard-Schnittstelle zw Applikation und Betriebssystem)

Seite 10

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Beenden von Prozessen bull Prozesse koumlnnen sich selbst durch den exit()-Systemaufruf beenden und damit aus

dem System entfernenbull Ein Prozess kann die von ihm erzeugten Prozesse beenden falls

ndash ein Prozess die ihm zugestandenen Betriebsmittel verbraucht hatndash ein Prozess nicht laumlnger gebraucht wird oder fallsndash der erzeugende Prozess sich beendet und es nicht gewuumlnscht oder erlaubt ist

dass die erzeugten Prozesse unabhaumlngig weiter existieren (cascading termination)bull Auf die Beendigung eines erzeugten Prozesses kann in POSIX-Systemen mit Hilfe des

wait() Systemaufrufs gewartet werdenbull Der Ergebniswert (return code) eines sich beendenden Prozesses wird an den

erzeugenden Prozess weitergeleitet

Seite 11

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

while (1) repeat forever type_prompt() display prompt on screen read_command() read input from the terminal

pid = fork() create a new

process if (pid lt 0) repeat if system call failed

perror(fork)continue

if (pid = 0) parent process

waitpid(pid ampstatus 0) wait for child

else child process execve(command params 0) execute

command

Beispiel einfacher Kommandointerpreter

als Sohnprozessals Vaterprozess

Seite 12

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Die 5 Taskzustaumlnde mit den wichtigsten Uumlbergaumlngen

dormant existent

ready bereit

running laufend terminated

beendet

suspended blockiert

Task ist der Prozessverwaltung bekannt gegeben

Task ist gestartet und alle Betriebsmittel vorhanden (eingeplant)

Betriebsmittel fehlen

Weitere Begriffe

Dormant = idle new

Existent = ruhend

Ready = runnable busy

Bereit = ablaufwillig rechenbereit

Running = executing

Laufend = ablaufend rechnend aktiv

Suspended = blocked waiting

Task ist abgearbeitet

Task ist eliminiert

Betriebsmittel vorhanden

Task ist der Prozessor zugeteilt

Task ist verdraumlngt

Seite 13

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Die 5 Taskzustaumlnde mit den wichtigsten Uumlbergaumlngen

dormant existent

ready bereit

running laufend terminated

beendet

suspended blockiert

admitted

IO or event wait

exit

Task ist eliminiert

IO or event completion

dispatch Interrupt trap

Seite 14

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Zustandsuumlbergaumlnge (Umhaumlngen in eine andere Liste) bull Es existieren drei Arten des Prozessor-Entzugs

ndash Aufgabe des Prozessors durch einen Warteaufruf Wartelistendash Verdraumlngung durch einen anderen Prozess (Praumlemption) Bereitlistendash Beendigung

bull Vom Zustand bdquoblockiertldquo geht es nicht direkt in den Zustand bdquorunningldquobull Der Uumlbergang von bdquorunningldquo nach bdquoblockiertldquo wird immer durch den Prozess selbst

initiiertbull Der Uumlbergang von bdquorunningldquo nach bdquobeendetldquo wird immer durch den Prozess selbst

initiiertbull Der Uumlbergang von bdquobereitldquo nach bdquorunningldquo und zuruumlck geschieht immer durch das

Betriebssystem

Seite 15

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Leichtgewichtsprozesse (Threads)bull Threads sind parallele Kontrollfluumlsse die nicht gegeneinander abgeschottet sind

ndash laufen innerhalb des Adressraums eines bdquoechtenldquo Rechenprozessesndash teilen sich gemeinsame Ressourcen (zB globale Variable)

bull Es gibt Threads im Betriebssystem-Kernel Scheduling durch BSbull Es gibt Threads im Usermodus des Betriebssystems Scheduling durch Anwendung

BS nur fuumlr Prozess-Scheduling verantwortlich

Kernel

Usermodus

Prozess

Thread

Seite 16

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Unterschiede zwischen Tasks und Threads

bull Aus Sicht der Betriebszustaumlnde der Zeitparameter des Schedulings und der Synchronisation sind Thread und Task gleich

Task Thread

Besitzer von Betriebsmitteln Kann auszliger Prozessor selbst keine Betriebsmittel besitzen verfuumlgt aber uumlber alle Betriebsmittel der Task der er angehoumlrt

Eigener Adressraum Adressraum der Task der er angehoumlrt Threads haben einen gemeinsamen Adressraum

Enthaumllt einen oder mehrere Tasks Element einer Task

Kommunikation uumlber Taskgrenzen hinaus bevorzugt uumlber Botschaften

Kommunikation zwischen den Threads bevorzugt uumlber gleiche Daten

Task wird charakterisiert uumlber einen PCB

Thread wird charakterisiert uumlber Programmzaumlhler Register Stack und Zustand

Seite 17

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Vorteile von Threadsbull Kontextwechsel zwischen Threads effizienter als zwischen Prozessen

ndash kein Wechsel des Adressraumsndash kein automatisches Schedulingndash kein Retten und Restaurieren des Kontextes (nur Programmzaumlhler und Register)

bull Pro Zeiteinheit sind viel mehr Threadwechsel als Prozesswechsel moumlglich deshalb auch bdquoleichtgewichtigeldquo Prozesse

bull Einfachere Programmierung (gegenuumlber Tasks) wenn mehrere gleichzeitige Aktivitaumlten von denen einige von Zeit zu Zeit blockieren modelliert werden muumlssen

bull Bessere Performance bei Erzeugung und Zerstoumlrung da keine Ressourcen mit Threads verbunden sind

bull Bessere Performance bei Mischung von CPU- mit IO-intensiven Aufgaben (kein Vorteil bei reiner CPU-Nutzung

bull ABER Da die Schutzfunktion der getrennten Adressraumlume fehlt werden Synchronisationsmechanismen benoumltigt

Seite 18

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselbull Zur Erinnerung

ndash Auf einem Rechner laufen mehrere Prozessendash Es gibt meist nur eine CPUndash Das heiszligt die Prozesse muumlssen sich in der Nutzung der CPU abwechselnndash Das Betriebssystem entscheidet welcher Prozess als naumlchstes die CPU benutzen

darfbull Komponenten des Scheduling

ndash Prozesswechselkostenndash Warteschlangenmodellendash Scheduling-Verfahren

Seite 19

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselkostenbull Ein Prozesswechsel zwischen 2 Prozessen A und B schlieszligt genau genommen drei

weitere mit einndash Prozess A Unterbrechungsbearbeitung (UB)ndash UB Betriebssystem (BS)ndash BS Prozess Bndash Prozess B BS

ndash BS Prozess A

BS

Unterbr

Prozess A

Prozess B

1 KW (Kontextwechsel)

2 KW

3 KW 4 KW

5 KW

Prozess A ist verdraumlngt

bull Beim Prozesswechsel muss der Kontext des Prozesses im PCB gesichert werden dh beim 1 PW save state into PCBA und reload state from PCBB

bull Prozesswechsel sind relativ teuer (zB 122 μs auf Sun Sparc 20) 2 Prozesswechsel1 Prozesswechsel

(PW)

Seite 20

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodellebull Prozesse werden intern in Warteschlangen gehalten wenn ihnen die angeforderten

Betriebsmittel (zB die CPU) nicht zur Verfuumlgung stehen oder die erwarteten Ereignisse (zB Beendigung eines Prozesses) noch nicht eingetreten sind

bull Die Auswahlstrategien der Warteschlangen haben wesentlichen Einfluss auf das Systemverhalten

bull Prozesse migrieren aus Sicht des Betriebssystems zwischen den verschiedenen Warteschlangen

ndash Job queue (Prozessliste) Menge aller Prozesse im Systemndash Ready queue (Bereitliste CPU-Warteschlange) Menge der Prozesse die im

Hauptspeicher geladen und bereit zur Ausfuumlhrung sindndash Device queues (Warteschlange fuumlr jedes Geraumlt) Menge der Prozesse die auf ein

IO-Geraumlt warten

Seite 21

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Prozesse migrieren zwischen den Warteschlangen

Seite 22

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Beispiel

Seite 23

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Seite 24

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Ankunftszeit Task wird in Taskliste aufgenommen

Anforderungszeit Ereignis tritt ein Task wird ablaufwilligStartzeit Task erhaumllt

erstmalig die CPU zugeteilt

Beendigungszeit Task hat Aufgabe erledigt und ruht wieder

Deadline Zeit zu der die Task spaumltestens beendet sein muss

Ausfuumlhrungszeit Rechenzeit der Task (ohne Wartezeiten)

Periode Zeitdifferenz zwischen aufeinander folgenden Anforderungen

Spielraum Restzeit zwischen Beendigung und Deadline

Reaktionszeit Zeit zwischen Anfor-derung und Start der Ausfuumlhrung

Seite 25

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

ai Ankunftszeit (Arrival Time) Zeitpunkt an dem eine Task dem Betriebssystem bekannt gemacht wird die Taskverwaltung nimmt die Task in die Taskliste und setzt sie in den Zustand ruhend

ri Anforderungszeit (Request Time) Die Task bewirbt sich bei der Taskverwaltung um den Prozessor

si Startzeit (Start Time) die Task erhaumllt den Prozessor zugeteilt

ci Beendigungszeit (Completion Time) Die Task hat ihre Aufgabe erledigt und kehrt in den Zustand ruhend zuruumlck

di Zeitschranke (Deadline) Zeitpunkt an dem die Taskausfuumlhrung spaumltestens beendet sein muss Die Zeitschranke kann hart fest oder weich sein

pi Periode (Period) Zeitdauer kennzeichnet die Wiederholungsrate bei periodischen Tasks sie ergibt sich aus der Zeitdifferenz zwischen zwei aufeinander folgenden Anforderungszeiten einer Task

ei Ausfuumlhrungszeit (Execution Time) Zeitdauer die eine Task zur Ausfuumlhrung ihrer Aufgabe benoumltigt wenn sie sich im Zustand laufend befindet Eine Variante ist die maximale Ausfuumlhrungszeit (worst case execution time = WCET) eine obere Schranke der Ausfuumlhrungszeit die in keinem Fall uumlberschritten werden darf

li Spielraum (Laxity) verbleibende Restzeit zwischen Beendigungszeit und Zeitschranke

ji Reaktionszeit (Reaction Time Release Jitter) Zeitraum kennzeichnet die Verzoumlgerung zwischen Anforderung und dem Start der Ausfuumlhrung

Seite 26

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Uumlbungsfragen (Vorl Uni Stuttgart)

1048709 Eine Task im Zustand ldquorunnablerdquo wird momentan ausgefuumlhrt

1048709 Ein Task-Zustand kann direkt von ldquorunningrdquo zu ldquodormantrdquo wechseln

1048709 Eine Task im Zustand ldquosuspendedrdquo kann direkt in den Zustand ldquorunningrdquo wechseln

1048709 Eine Task im Zustand ldquodormantrdquo ist nicht bereit da Zeit- oder andere Bedingungen nicht

erfuumlllt sind

1048709 Eine Task im Zustand ldquosuspendedrdquo wartet auf das Auftreten eines Events

Seite 6

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Kooperatives Multitasking

bull Jeder Prozess gibt seinen Status freiwillig an naumlchsten Prozess weiterbull Wenn Prozess 1 fertig ist gibt er dies an Prozess 2 weiter und

wechselt in den Status rechenbereit waumlhrend der Prozess 2 von rechenbereit auf rechnend wechselt

bull Bsp Eine Runde von Indianern die die Friedenspfeife rauchtbull Jeder Indianer in diesem Kreis stellt einen Prozess (alle rechenbereit)

dar und die Friedenspfeife stellt Rechenzeit dar

bull Rauchender Indianer entspricht dem Zustand rechnend alle anderen Indianer sind rechenbereit da sie auf die Pfeife warten

bull Das Kooperative an diesem System ist dass jeder Indianer nachdem er eine Weile geraucht hat die Pfeife freiwillig an den naumlchsten Indianer weitergibt

bull Hieraus wird auch der Nachteil des Systems sichtbar Kann oder will ein Indianer die Pfeife nicht weiterreichen kommt das System zum erliegen

bull Vorteil leicht implementierbar

Seite 7

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Praumlemptives Multitasking

bull Jedem Prozess wird bestimmtes Zeitfenster gegeben in dem er ausgefuumlhrt wird am Ende der Zeit wird der Prozess unterbrochen

bull Teil des Betriebssystems kuumlmmert sich um Wechseln zum naumlchsten Prozess und gibt dem naumlchsten auszufuumlhrenden Prozess die Kontrolle bis zum Ende des Zeitfensters

bull Bsp Haumluptling nimmt selbst die Pfeife in die Hand und reicht sie von Indianer zu Indianer weiter ohne sie aus der Hand zu geben

bull Da sich keiner zu widersprechen getraut ist der ordnungsgemaumlszlige Ablauf sichergestellt

bull Haumluptling fungiert als Interrupt der regelmaumlszligig ISR (Interrupt Service Routine sbquoPfeife weiterreichenrsquo aufruft

bull Dann gibt er dem jeweiligen Indianer der nun rauchen darf den Status running bis er ihn wieder unterbricht

bull Nachteil des Systems mehr Programmieraufwand

bull Vorteil stabil funktionierendes System

Seite 8

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Schedulerbull Bestandteil des Betriebssystemsbull sinnvolle Verteilung der CPU Zeit an aktive Prozessebull verantwortlich fuumlr die Umsetzung von Multitasking

Ziele des Schedulers (die sich jedoch im Einzelfall widersprechen koumlnnen) bull Fairness jeder Prozess soll einen gerechten Anteil an der CPU-Leistung bekommen dh

kein Prozess wird dauerhaft benachteiligtbull Effizienz CPU sollte dauerhaft belegt werdenbull Antwortzeit Antwortzeit soll fuumlr interaktive Benutzer minimal seinbull Durchsatz Anzahl der bearbeiteten Prozesse pro Zeitintervall soll maximiert werden (=

die zur Verfuumlgung stehenden Ressourcen sollen optimal ausgelastet werden)bull Verweilzeit Verweildauer von Programmen soll moumlglichst gering seinbull Terminerfuumlllung Prozesse die zu einem bestimmten Termin beendet sein

muumlssen werden so geplant dass der Termin eingehalten wird

Seite 9

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Erzeugen von Prozessen bull Prozesse werden erzeugt bei

ndash Initialisierung des Systems (einfache Systeme zB Steuerung eines Mikrowellenherds)

ndash Systemaufruf zum Erzeugen eines (Sohn-)Prozesses durch einen anderen (Vater-)Prozess

ndash Benutzeranfrage einen neuen Prozess zu erzeugenndash Initiierung einer Stapelverarbeitung (Batch-Job)

bull POSIX-Systeme benutzen hierzu den fork() Systemaufrufndash Der neu erzeugte Prozess (child) ist eine exakte Kopie des erzeugenden Prozesses (parent)

besitzt aber eine neue Prozessnummerndash Beide Prozesse fuumlhren dieselben Instruktionen nach dem fork() ausndash Der Ergebniswert des fork() Systemaufrufs ist in beiden Prozessen unterschiedlichndash Mittels des Systemaufrufs exec() koumlnnen in einem Prozess neue Programme gestartet

werden

bull Windows Systemaufruf CreateProcess()bull Da beliebige Prozesse neue Prozesse erzeugen koumlnnen entsteht eine Hierarchie

(Baum) von Prozessen die als verkettete Liste organisiert ist(POSIX = Portable Operating System Interface (Standard-Schnittstelle zw Applikation und Betriebssystem)

Seite 10

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Beenden von Prozessen bull Prozesse koumlnnen sich selbst durch den exit()-Systemaufruf beenden und damit aus

dem System entfernenbull Ein Prozess kann die von ihm erzeugten Prozesse beenden falls

ndash ein Prozess die ihm zugestandenen Betriebsmittel verbraucht hatndash ein Prozess nicht laumlnger gebraucht wird oder fallsndash der erzeugende Prozess sich beendet und es nicht gewuumlnscht oder erlaubt ist

dass die erzeugten Prozesse unabhaumlngig weiter existieren (cascading termination)bull Auf die Beendigung eines erzeugten Prozesses kann in POSIX-Systemen mit Hilfe des

wait() Systemaufrufs gewartet werdenbull Der Ergebniswert (return code) eines sich beendenden Prozesses wird an den

erzeugenden Prozess weitergeleitet

Seite 11

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

while (1) repeat forever type_prompt() display prompt on screen read_command() read input from the terminal

pid = fork() create a new

process if (pid lt 0) repeat if system call failed

perror(fork)continue

if (pid = 0) parent process

waitpid(pid ampstatus 0) wait for child

else child process execve(command params 0) execute

command

Beispiel einfacher Kommandointerpreter

als Sohnprozessals Vaterprozess

Seite 12

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Die 5 Taskzustaumlnde mit den wichtigsten Uumlbergaumlngen

dormant existent

ready bereit

running laufend terminated

beendet

suspended blockiert

Task ist der Prozessverwaltung bekannt gegeben

Task ist gestartet und alle Betriebsmittel vorhanden (eingeplant)

Betriebsmittel fehlen

Weitere Begriffe

Dormant = idle new

Existent = ruhend

Ready = runnable busy

Bereit = ablaufwillig rechenbereit

Running = executing

Laufend = ablaufend rechnend aktiv

Suspended = blocked waiting

Task ist abgearbeitet

Task ist eliminiert

Betriebsmittel vorhanden

Task ist der Prozessor zugeteilt

Task ist verdraumlngt

Seite 13

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Die 5 Taskzustaumlnde mit den wichtigsten Uumlbergaumlngen

dormant existent

ready bereit

running laufend terminated

beendet

suspended blockiert

admitted

IO or event wait

exit

Task ist eliminiert

IO or event completion

dispatch Interrupt trap

Seite 14

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Zustandsuumlbergaumlnge (Umhaumlngen in eine andere Liste) bull Es existieren drei Arten des Prozessor-Entzugs

ndash Aufgabe des Prozessors durch einen Warteaufruf Wartelistendash Verdraumlngung durch einen anderen Prozess (Praumlemption) Bereitlistendash Beendigung

bull Vom Zustand bdquoblockiertldquo geht es nicht direkt in den Zustand bdquorunningldquobull Der Uumlbergang von bdquorunningldquo nach bdquoblockiertldquo wird immer durch den Prozess selbst

initiiertbull Der Uumlbergang von bdquorunningldquo nach bdquobeendetldquo wird immer durch den Prozess selbst

initiiertbull Der Uumlbergang von bdquobereitldquo nach bdquorunningldquo und zuruumlck geschieht immer durch das

Betriebssystem

Seite 15

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Leichtgewichtsprozesse (Threads)bull Threads sind parallele Kontrollfluumlsse die nicht gegeneinander abgeschottet sind

ndash laufen innerhalb des Adressraums eines bdquoechtenldquo Rechenprozessesndash teilen sich gemeinsame Ressourcen (zB globale Variable)

bull Es gibt Threads im Betriebssystem-Kernel Scheduling durch BSbull Es gibt Threads im Usermodus des Betriebssystems Scheduling durch Anwendung

BS nur fuumlr Prozess-Scheduling verantwortlich

Kernel

Usermodus

Prozess

Thread

Seite 16

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Unterschiede zwischen Tasks und Threads

bull Aus Sicht der Betriebszustaumlnde der Zeitparameter des Schedulings und der Synchronisation sind Thread und Task gleich

Task Thread

Besitzer von Betriebsmitteln Kann auszliger Prozessor selbst keine Betriebsmittel besitzen verfuumlgt aber uumlber alle Betriebsmittel der Task der er angehoumlrt

Eigener Adressraum Adressraum der Task der er angehoumlrt Threads haben einen gemeinsamen Adressraum

Enthaumllt einen oder mehrere Tasks Element einer Task

Kommunikation uumlber Taskgrenzen hinaus bevorzugt uumlber Botschaften

Kommunikation zwischen den Threads bevorzugt uumlber gleiche Daten

Task wird charakterisiert uumlber einen PCB

Thread wird charakterisiert uumlber Programmzaumlhler Register Stack und Zustand

Seite 17

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Vorteile von Threadsbull Kontextwechsel zwischen Threads effizienter als zwischen Prozessen

ndash kein Wechsel des Adressraumsndash kein automatisches Schedulingndash kein Retten und Restaurieren des Kontextes (nur Programmzaumlhler und Register)

bull Pro Zeiteinheit sind viel mehr Threadwechsel als Prozesswechsel moumlglich deshalb auch bdquoleichtgewichtigeldquo Prozesse

bull Einfachere Programmierung (gegenuumlber Tasks) wenn mehrere gleichzeitige Aktivitaumlten von denen einige von Zeit zu Zeit blockieren modelliert werden muumlssen

bull Bessere Performance bei Erzeugung und Zerstoumlrung da keine Ressourcen mit Threads verbunden sind

bull Bessere Performance bei Mischung von CPU- mit IO-intensiven Aufgaben (kein Vorteil bei reiner CPU-Nutzung

bull ABER Da die Schutzfunktion der getrennten Adressraumlume fehlt werden Synchronisationsmechanismen benoumltigt

Seite 18

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselbull Zur Erinnerung

ndash Auf einem Rechner laufen mehrere Prozessendash Es gibt meist nur eine CPUndash Das heiszligt die Prozesse muumlssen sich in der Nutzung der CPU abwechselnndash Das Betriebssystem entscheidet welcher Prozess als naumlchstes die CPU benutzen

darfbull Komponenten des Scheduling

ndash Prozesswechselkostenndash Warteschlangenmodellendash Scheduling-Verfahren

Seite 19

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselkostenbull Ein Prozesswechsel zwischen 2 Prozessen A und B schlieszligt genau genommen drei

weitere mit einndash Prozess A Unterbrechungsbearbeitung (UB)ndash UB Betriebssystem (BS)ndash BS Prozess Bndash Prozess B BS

ndash BS Prozess A

BS

Unterbr

Prozess A

Prozess B

1 KW (Kontextwechsel)

2 KW

3 KW 4 KW

5 KW

Prozess A ist verdraumlngt

bull Beim Prozesswechsel muss der Kontext des Prozesses im PCB gesichert werden dh beim 1 PW save state into PCBA und reload state from PCBB

bull Prozesswechsel sind relativ teuer (zB 122 μs auf Sun Sparc 20) 2 Prozesswechsel1 Prozesswechsel

(PW)

Seite 20

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodellebull Prozesse werden intern in Warteschlangen gehalten wenn ihnen die angeforderten

Betriebsmittel (zB die CPU) nicht zur Verfuumlgung stehen oder die erwarteten Ereignisse (zB Beendigung eines Prozesses) noch nicht eingetreten sind

bull Die Auswahlstrategien der Warteschlangen haben wesentlichen Einfluss auf das Systemverhalten

bull Prozesse migrieren aus Sicht des Betriebssystems zwischen den verschiedenen Warteschlangen

ndash Job queue (Prozessliste) Menge aller Prozesse im Systemndash Ready queue (Bereitliste CPU-Warteschlange) Menge der Prozesse die im

Hauptspeicher geladen und bereit zur Ausfuumlhrung sindndash Device queues (Warteschlange fuumlr jedes Geraumlt) Menge der Prozesse die auf ein

IO-Geraumlt warten

Seite 21

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Prozesse migrieren zwischen den Warteschlangen

Seite 22

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Beispiel

Seite 23

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Seite 24

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Ankunftszeit Task wird in Taskliste aufgenommen

Anforderungszeit Ereignis tritt ein Task wird ablaufwilligStartzeit Task erhaumllt

erstmalig die CPU zugeteilt

Beendigungszeit Task hat Aufgabe erledigt und ruht wieder

Deadline Zeit zu der die Task spaumltestens beendet sein muss

Ausfuumlhrungszeit Rechenzeit der Task (ohne Wartezeiten)

Periode Zeitdifferenz zwischen aufeinander folgenden Anforderungen

Spielraum Restzeit zwischen Beendigung und Deadline

Reaktionszeit Zeit zwischen Anfor-derung und Start der Ausfuumlhrung

Seite 25

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

ai Ankunftszeit (Arrival Time) Zeitpunkt an dem eine Task dem Betriebssystem bekannt gemacht wird die Taskverwaltung nimmt die Task in die Taskliste und setzt sie in den Zustand ruhend

ri Anforderungszeit (Request Time) Die Task bewirbt sich bei der Taskverwaltung um den Prozessor

si Startzeit (Start Time) die Task erhaumllt den Prozessor zugeteilt

ci Beendigungszeit (Completion Time) Die Task hat ihre Aufgabe erledigt und kehrt in den Zustand ruhend zuruumlck

di Zeitschranke (Deadline) Zeitpunkt an dem die Taskausfuumlhrung spaumltestens beendet sein muss Die Zeitschranke kann hart fest oder weich sein

pi Periode (Period) Zeitdauer kennzeichnet die Wiederholungsrate bei periodischen Tasks sie ergibt sich aus der Zeitdifferenz zwischen zwei aufeinander folgenden Anforderungszeiten einer Task

ei Ausfuumlhrungszeit (Execution Time) Zeitdauer die eine Task zur Ausfuumlhrung ihrer Aufgabe benoumltigt wenn sie sich im Zustand laufend befindet Eine Variante ist die maximale Ausfuumlhrungszeit (worst case execution time = WCET) eine obere Schranke der Ausfuumlhrungszeit die in keinem Fall uumlberschritten werden darf

li Spielraum (Laxity) verbleibende Restzeit zwischen Beendigungszeit und Zeitschranke

ji Reaktionszeit (Reaction Time Release Jitter) Zeitraum kennzeichnet die Verzoumlgerung zwischen Anforderung und dem Start der Ausfuumlhrung

Seite 26

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Uumlbungsfragen (Vorl Uni Stuttgart)

1048709 Eine Task im Zustand ldquorunnablerdquo wird momentan ausgefuumlhrt

1048709 Ein Task-Zustand kann direkt von ldquorunningrdquo zu ldquodormantrdquo wechseln

1048709 Eine Task im Zustand ldquosuspendedrdquo kann direkt in den Zustand ldquorunningrdquo wechseln

1048709 Eine Task im Zustand ldquodormantrdquo ist nicht bereit da Zeit- oder andere Bedingungen nicht

erfuumlllt sind

1048709 Eine Task im Zustand ldquosuspendedrdquo wartet auf das Auftreten eines Events

Seite 7

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Praumlemptives Multitasking

bull Jedem Prozess wird bestimmtes Zeitfenster gegeben in dem er ausgefuumlhrt wird am Ende der Zeit wird der Prozess unterbrochen

bull Teil des Betriebssystems kuumlmmert sich um Wechseln zum naumlchsten Prozess und gibt dem naumlchsten auszufuumlhrenden Prozess die Kontrolle bis zum Ende des Zeitfensters

bull Bsp Haumluptling nimmt selbst die Pfeife in die Hand und reicht sie von Indianer zu Indianer weiter ohne sie aus der Hand zu geben

bull Da sich keiner zu widersprechen getraut ist der ordnungsgemaumlszlige Ablauf sichergestellt

bull Haumluptling fungiert als Interrupt der regelmaumlszligig ISR (Interrupt Service Routine sbquoPfeife weiterreichenrsquo aufruft

bull Dann gibt er dem jeweiligen Indianer der nun rauchen darf den Status running bis er ihn wieder unterbricht

bull Nachteil des Systems mehr Programmieraufwand

bull Vorteil stabil funktionierendes System

Seite 8

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Schedulerbull Bestandteil des Betriebssystemsbull sinnvolle Verteilung der CPU Zeit an aktive Prozessebull verantwortlich fuumlr die Umsetzung von Multitasking

Ziele des Schedulers (die sich jedoch im Einzelfall widersprechen koumlnnen) bull Fairness jeder Prozess soll einen gerechten Anteil an der CPU-Leistung bekommen dh

kein Prozess wird dauerhaft benachteiligtbull Effizienz CPU sollte dauerhaft belegt werdenbull Antwortzeit Antwortzeit soll fuumlr interaktive Benutzer minimal seinbull Durchsatz Anzahl der bearbeiteten Prozesse pro Zeitintervall soll maximiert werden (=

die zur Verfuumlgung stehenden Ressourcen sollen optimal ausgelastet werden)bull Verweilzeit Verweildauer von Programmen soll moumlglichst gering seinbull Terminerfuumlllung Prozesse die zu einem bestimmten Termin beendet sein

muumlssen werden so geplant dass der Termin eingehalten wird

Seite 9

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Erzeugen von Prozessen bull Prozesse werden erzeugt bei

ndash Initialisierung des Systems (einfache Systeme zB Steuerung eines Mikrowellenherds)

ndash Systemaufruf zum Erzeugen eines (Sohn-)Prozesses durch einen anderen (Vater-)Prozess

ndash Benutzeranfrage einen neuen Prozess zu erzeugenndash Initiierung einer Stapelverarbeitung (Batch-Job)

bull POSIX-Systeme benutzen hierzu den fork() Systemaufrufndash Der neu erzeugte Prozess (child) ist eine exakte Kopie des erzeugenden Prozesses (parent)

besitzt aber eine neue Prozessnummerndash Beide Prozesse fuumlhren dieselben Instruktionen nach dem fork() ausndash Der Ergebniswert des fork() Systemaufrufs ist in beiden Prozessen unterschiedlichndash Mittels des Systemaufrufs exec() koumlnnen in einem Prozess neue Programme gestartet

werden

bull Windows Systemaufruf CreateProcess()bull Da beliebige Prozesse neue Prozesse erzeugen koumlnnen entsteht eine Hierarchie

(Baum) von Prozessen die als verkettete Liste organisiert ist(POSIX = Portable Operating System Interface (Standard-Schnittstelle zw Applikation und Betriebssystem)

Seite 10

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Beenden von Prozessen bull Prozesse koumlnnen sich selbst durch den exit()-Systemaufruf beenden und damit aus

dem System entfernenbull Ein Prozess kann die von ihm erzeugten Prozesse beenden falls

ndash ein Prozess die ihm zugestandenen Betriebsmittel verbraucht hatndash ein Prozess nicht laumlnger gebraucht wird oder fallsndash der erzeugende Prozess sich beendet und es nicht gewuumlnscht oder erlaubt ist

dass die erzeugten Prozesse unabhaumlngig weiter existieren (cascading termination)bull Auf die Beendigung eines erzeugten Prozesses kann in POSIX-Systemen mit Hilfe des

wait() Systemaufrufs gewartet werdenbull Der Ergebniswert (return code) eines sich beendenden Prozesses wird an den

erzeugenden Prozess weitergeleitet

Seite 11

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

while (1) repeat forever type_prompt() display prompt on screen read_command() read input from the terminal

pid = fork() create a new

process if (pid lt 0) repeat if system call failed

perror(fork)continue

if (pid = 0) parent process

waitpid(pid ampstatus 0) wait for child

else child process execve(command params 0) execute

command

Beispiel einfacher Kommandointerpreter

als Sohnprozessals Vaterprozess

Seite 12

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Die 5 Taskzustaumlnde mit den wichtigsten Uumlbergaumlngen

dormant existent

ready bereit

running laufend terminated

beendet

suspended blockiert

Task ist der Prozessverwaltung bekannt gegeben

Task ist gestartet und alle Betriebsmittel vorhanden (eingeplant)

Betriebsmittel fehlen

Weitere Begriffe

Dormant = idle new

Existent = ruhend

Ready = runnable busy

Bereit = ablaufwillig rechenbereit

Running = executing

Laufend = ablaufend rechnend aktiv

Suspended = blocked waiting

Task ist abgearbeitet

Task ist eliminiert

Betriebsmittel vorhanden

Task ist der Prozessor zugeteilt

Task ist verdraumlngt

Seite 13

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Die 5 Taskzustaumlnde mit den wichtigsten Uumlbergaumlngen

dormant existent

ready bereit

running laufend terminated

beendet

suspended blockiert

admitted

IO or event wait

exit

Task ist eliminiert

IO or event completion

dispatch Interrupt trap

Seite 14

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Zustandsuumlbergaumlnge (Umhaumlngen in eine andere Liste) bull Es existieren drei Arten des Prozessor-Entzugs

ndash Aufgabe des Prozessors durch einen Warteaufruf Wartelistendash Verdraumlngung durch einen anderen Prozess (Praumlemption) Bereitlistendash Beendigung

bull Vom Zustand bdquoblockiertldquo geht es nicht direkt in den Zustand bdquorunningldquobull Der Uumlbergang von bdquorunningldquo nach bdquoblockiertldquo wird immer durch den Prozess selbst

initiiertbull Der Uumlbergang von bdquorunningldquo nach bdquobeendetldquo wird immer durch den Prozess selbst

initiiertbull Der Uumlbergang von bdquobereitldquo nach bdquorunningldquo und zuruumlck geschieht immer durch das

Betriebssystem

Seite 15

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Leichtgewichtsprozesse (Threads)bull Threads sind parallele Kontrollfluumlsse die nicht gegeneinander abgeschottet sind

ndash laufen innerhalb des Adressraums eines bdquoechtenldquo Rechenprozessesndash teilen sich gemeinsame Ressourcen (zB globale Variable)

bull Es gibt Threads im Betriebssystem-Kernel Scheduling durch BSbull Es gibt Threads im Usermodus des Betriebssystems Scheduling durch Anwendung

BS nur fuumlr Prozess-Scheduling verantwortlich

Kernel

Usermodus

Prozess

Thread

Seite 16

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Unterschiede zwischen Tasks und Threads

bull Aus Sicht der Betriebszustaumlnde der Zeitparameter des Schedulings und der Synchronisation sind Thread und Task gleich

Task Thread

Besitzer von Betriebsmitteln Kann auszliger Prozessor selbst keine Betriebsmittel besitzen verfuumlgt aber uumlber alle Betriebsmittel der Task der er angehoumlrt

Eigener Adressraum Adressraum der Task der er angehoumlrt Threads haben einen gemeinsamen Adressraum

Enthaumllt einen oder mehrere Tasks Element einer Task

Kommunikation uumlber Taskgrenzen hinaus bevorzugt uumlber Botschaften

Kommunikation zwischen den Threads bevorzugt uumlber gleiche Daten

Task wird charakterisiert uumlber einen PCB

Thread wird charakterisiert uumlber Programmzaumlhler Register Stack und Zustand

Seite 17

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Vorteile von Threadsbull Kontextwechsel zwischen Threads effizienter als zwischen Prozessen

ndash kein Wechsel des Adressraumsndash kein automatisches Schedulingndash kein Retten und Restaurieren des Kontextes (nur Programmzaumlhler und Register)

bull Pro Zeiteinheit sind viel mehr Threadwechsel als Prozesswechsel moumlglich deshalb auch bdquoleichtgewichtigeldquo Prozesse

bull Einfachere Programmierung (gegenuumlber Tasks) wenn mehrere gleichzeitige Aktivitaumlten von denen einige von Zeit zu Zeit blockieren modelliert werden muumlssen

bull Bessere Performance bei Erzeugung und Zerstoumlrung da keine Ressourcen mit Threads verbunden sind

bull Bessere Performance bei Mischung von CPU- mit IO-intensiven Aufgaben (kein Vorteil bei reiner CPU-Nutzung

bull ABER Da die Schutzfunktion der getrennten Adressraumlume fehlt werden Synchronisationsmechanismen benoumltigt

Seite 18

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselbull Zur Erinnerung

ndash Auf einem Rechner laufen mehrere Prozessendash Es gibt meist nur eine CPUndash Das heiszligt die Prozesse muumlssen sich in der Nutzung der CPU abwechselnndash Das Betriebssystem entscheidet welcher Prozess als naumlchstes die CPU benutzen

darfbull Komponenten des Scheduling

ndash Prozesswechselkostenndash Warteschlangenmodellendash Scheduling-Verfahren

Seite 19

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselkostenbull Ein Prozesswechsel zwischen 2 Prozessen A und B schlieszligt genau genommen drei

weitere mit einndash Prozess A Unterbrechungsbearbeitung (UB)ndash UB Betriebssystem (BS)ndash BS Prozess Bndash Prozess B BS

ndash BS Prozess A

BS

Unterbr

Prozess A

Prozess B

1 KW (Kontextwechsel)

2 KW

3 KW 4 KW

5 KW

Prozess A ist verdraumlngt

bull Beim Prozesswechsel muss der Kontext des Prozesses im PCB gesichert werden dh beim 1 PW save state into PCBA und reload state from PCBB

bull Prozesswechsel sind relativ teuer (zB 122 μs auf Sun Sparc 20) 2 Prozesswechsel1 Prozesswechsel

(PW)

Seite 20

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodellebull Prozesse werden intern in Warteschlangen gehalten wenn ihnen die angeforderten

Betriebsmittel (zB die CPU) nicht zur Verfuumlgung stehen oder die erwarteten Ereignisse (zB Beendigung eines Prozesses) noch nicht eingetreten sind

bull Die Auswahlstrategien der Warteschlangen haben wesentlichen Einfluss auf das Systemverhalten

bull Prozesse migrieren aus Sicht des Betriebssystems zwischen den verschiedenen Warteschlangen

ndash Job queue (Prozessliste) Menge aller Prozesse im Systemndash Ready queue (Bereitliste CPU-Warteschlange) Menge der Prozesse die im

Hauptspeicher geladen und bereit zur Ausfuumlhrung sindndash Device queues (Warteschlange fuumlr jedes Geraumlt) Menge der Prozesse die auf ein

IO-Geraumlt warten

Seite 21

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Prozesse migrieren zwischen den Warteschlangen

Seite 22

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Beispiel

Seite 23

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Seite 24

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Ankunftszeit Task wird in Taskliste aufgenommen

Anforderungszeit Ereignis tritt ein Task wird ablaufwilligStartzeit Task erhaumllt

erstmalig die CPU zugeteilt

Beendigungszeit Task hat Aufgabe erledigt und ruht wieder

Deadline Zeit zu der die Task spaumltestens beendet sein muss

Ausfuumlhrungszeit Rechenzeit der Task (ohne Wartezeiten)

Periode Zeitdifferenz zwischen aufeinander folgenden Anforderungen

Spielraum Restzeit zwischen Beendigung und Deadline

Reaktionszeit Zeit zwischen Anfor-derung und Start der Ausfuumlhrung

Seite 25

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

ai Ankunftszeit (Arrival Time) Zeitpunkt an dem eine Task dem Betriebssystem bekannt gemacht wird die Taskverwaltung nimmt die Task in die Taskliste und setzt sie in den Zustand ruhend

ri Anforderungszeit (Request Time) Die Task bewirbt sich bei der Taskverwaltung um den Prozessor

si Startzeit (Start Time) die Task erhaumllt den Prozessor zugeteilt

ci Beendigungszeit (Completion Time) Die Task hat ihre Aufgabe erledigt und kehrt in den Zustand ruhend zuruumlck

di Zeitschranke (Deadline) Zeitpunkt an dem die Taskausfuumlhrung spaumltestens beendet sein muss Die Zeitschranke kann hart fest oder weich sein

pi Periode (Period) Zeitdauer kennzeichnet die Wiederholungsrate bei periodischen Tasks sie ergibt sich aus der Zeitdifferenz zwischen zwei aufeinander folgenden Anforderungszeiten einer Task

ei Ausfuumlhrungszeit (Execution Time) Zeitdauer die eine Task zur Ausfuumlhrung ihrer Aufgabe benoumltigt wenn sie sich im Zustand laufend befindet Eine Variante ist die maximale Ausfuumlhrungszeit (worst case execution time = WCET) eine obere Schranke der Ausfuumlhrungszeit die in keinem Fall uumlberschritten werden darf

li Spielraum (Laxity) verbleibende Restzeit zwischen Beendigungszeit und Zeitschranke

ji Reaktionszeit (Reaction Time Release Jitter) Zeitraum kennzeichnet die Verzoumlgerung zwischen Anforderung und dem Start der Ausfuumlhrung

Seite 26

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Uumlbungsfragen (Vorl Uni Stuttgart)

1048709 Eine Task im Zustand ldquorunnablerdquo wird momentan ausgefuumlhrt

1048709 Ein Task-Zustand kann direkt von ldquorunningrdquo zu ldquodormantrdquo wechseln

1048709 Eine Task im Zustand ldquosuspendedrdquo kann direkt in den Zustand ldquorunningrdquo wechseln

1048709 Eine Task im Zustand ldquodormantrdquo ist nicht bereit da Zeit- oder andere Bedingungen nicht

erfuumlllt sind

1048709 Eine Task im Zustand ldquosuspendedrdquo wartet auf das Auftreten eines Events

Seite 8

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Schedulerbull Bestandteil des Betriebssystemsbull sinnvolle Verteilung der CPU Zeit an aktive Prozessebull verantwortlich fuumlr die Umsetzung von Multitasking

Ziele des Schedulers (die sich jedoch im Einzelfall widersprechen koumlnnen) bull Fairness jeder Prozess soll einen gerechten Anteil an der CPU-Leistung bekommen dh

kein Prozess wird dauerhaft benachteiligtbull Effizienz CPU sollte dauerhaft belegt werdenbull Antwortzeit Antwortzeit soll fuumlr interaktive Benutzer minimal seinbull Durchsatz Anzahl der bearbeiteten Prozesse pro Zeitintervall soll maximiert werden (=

die zur Verfuumlgung stehenden Ressourcen sollen optimal ausgelastet werden)bull Verweilzeit Verweildauer von Programmen soll moumlglichst gering seinbull Terminerfuumlllung Prozesse die zu einem bestimmten Termin beendet sein

muumlssen werden so geplant dass der Termin eingehalten wird

Seite 9

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Erzeugen von Prozessen bull Prozesse werden erzeugt bei

ndash Initialisierung des Systems (einfache Systeme zB Steuerung eines Mikrowellenherds)

ndash Systemaufruf zum Erzeugen eines (Sohn-)Prozesses durch einen anderen (Vater-)Prozess

ndash Benutzeranfrage einen neuen Prozess zu erzeugenndash Initiierung einer Stapelverarbeitung (Batch-Job)

bull POSIX-Systeme benutzen hierzu den fork() Systemaufrufndash Der neu erzeugte Prozess (child) ist eine exakte Kopie des erzeugenden Prozesses (parent)

besitzt aber eine neue Prozessnummerndash Beide Prozesse fuumlhren dieselben Instruktionen nach dem fork() ausndash Der Ergebniswert des fork() Systemaufrufs ist in beiden Prozessen unterschiedlichndash Mittels des Systemaufrufs exec() koumlnnen in einem Prozess neue Programme gestartet

werden

bull Windows Systemaufruf CreateProcess()bull Da beliebige Prozesse neue Prozesse erzeugen koumlnnen entsteht eine Hierarchie

(Baum) von Prozessen die als verkettete Liste organisiert ist(POSIX = Portable Operating System Interface (Standard-Schnittstelle zw Applikation und Betriebssystem)

Seite 10

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Beenden von Prozessen bull Prozesse koumlnnen sich selbst durch den exit()-Systemaufruf beenden und damit aus

dem System entfernenbull Ein Prozess kann die von ihm erzeugten Prozesse beenden falls

ndash ein Prozess die ihm zugestandenen Betriebsmittel verbraucht hatndash ein Prozess nicht laumlnger gebraucht wird oder fallsndash der erzeugende Prozess sich beendet und es nicht gewuumlnscht oder erlaubt ist

dass die erzeugten Prozesse unabhaumlngig weiter existieren (cascading termination)bull Auf die Beendigung eines erzeugten Prozesses kann in POSIX-Systemen mit Hilfe des

wait() Systemaufrufs gewartet werdenbull Der Ergebniswert (return code) eines sich beendenden Prozesses wird an den

erzeugenden Prozess weitergeleitet

Seite 11

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

while (1) repeat forever type_prompt() display prompt on screen read_command() read input from the terminal

pid = fork() create a new

process if (pid lt 0) repeat if system call failed

perror(fork)continue

if (pid = 0) parent process

waitpid(pid ampstatus 0) wait for child

else child process execve(command params 0) execute

command

Beispiel einfacher Kommandointerpreter

als Sohnprozessals Vaterprozess

Seite 12

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Die 5 Taskzustaumlnde mit den wichtigsten Uumlbergaumlngen

dormant existent

ready bereit

running laufend terminated

beendet

suspended blockiert

Task ist der Prozessverwaltung bekannt gegeben

Task ist gestartet und alle Betriebsmittel vorhanden (eingeplant)

Betriebsmittel fehlen

Weitere Begriffe

Dormant = idle new

Existent = ruhend

Ready = runnable busy

Bereit = ablaufwillig rechenbereit

Running = executing

Laufend = ablaufend rechnend aktiv

Suspended = blocked waiting

Task ist abgearbeitet

Task ist eliminiert

Betriebsmittel vorhanden

Task ist der Prozessor zugeteilt

Task ist verdraumlngt

Seite 13

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Die 5 Taskzustaumlnde mit den wichtigsten Uumlbergaumlngen

dormant existent

ready bereit

running laufend terminated

beendet

suspended blockiert

admitted

IO or event wait

exit

Task ist eliminiert

IO or event completion

dispatch Interrupt trap

Seite 14

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Zustandsuumlbergaumlnge (Umhaumlngen in eine andere Liste) bull Es existieren drei Arten des Prozessor-Entzugs

ndash Aufgabe des Prozessors durch einen Warteaufruf Wartelistendash Verdraumlngung durch einen anderen Prozess (Praumlemption) Bereitlistendash Beendigung

bull Vom Zustand bdquoblockiertldquo geht es nicht direkt in den Zustand bdquorunningldquobull Der Uumlbergang von bdquorunningldquo nach bdquoblockiertldquo wird immer durch den Prozess selbst

initiiertbull Der Uumlbergang von bdquorunningldquo nach bdquobeendetldquo wird immer durch den Prozess selbst

initiiertbull Der Uumlbergang von bdquobereitldquo nach bdquorunningldquo und zuruumlck geschieht immer durch das

Betriebssystem

Seite 15

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Leichtgewichtsprozesse (Threads)bull Threads sind parallele Kontrollfluumlsse die nicht gegeneinander abgeschottet sind

ndash laufen innerhalb des Adressraums eines bdquoechtenldquo Rechenprozessesndash teilen sich gemeinsame Ressourcen (zB globale Variable)

bull Es gibt Threads im Betriebssystem-Kernel Scheduling durch BSbull Es gibt Threads im Usermodus des Betriebssystems Scheduling durch Anwendung

BS nur fuumlr Prozess-Scheduling verantwortlich

Kernel

Usermodus

Prozess

Thread

Seite 16

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Unterschiede zwischen Tasks und Threads

bull Aus Sicht der Betriebszustaumlnde der Zeitparameter des Schedulings und der Synchronisation sind Thread und Task gleich

Task Thread

Besitzer von Betriebsmitteln Kann auszliger Prozessor selbst keine Betriebsmittel besitzen verfuumlgt aber uumlber alle Betriebsmittel der Task der er angehoumlrt

Eigener Adressraum Adressraum der Task der er angehoumlrt Threads haben einen gemeinsamen Adressraum

Enthaumllt einen oder mehrere Tasks Element einer Task

Kommunikation uumlber Taskgrenzen hinaus bevorzugt uumlber Botschaften

Kommunikation zwischen den Threads bevorzugt uumlber gleiche Daten

Task wird charakterisiert uumlber einen PCB

Thread wird charakterisiert uumlber Programmzaumlhler Register Stack und Zustand

Seite 17

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Vorteile von Threadsbull Kontextwechsel zwischen Threads effizienter als zwischen Prozessen

ndash kein Wechsel des Adressraumsndash kein automatisches Schedulingndash kein Retten und Restaurieren des Kontextes (nur Programmzaumlhler und Register)

bull Pro Zeiteinheit sind viel mehr Threadwechsel als Prozesswechsel moumlglich deshalb auch bdquoleichtgewichtigeldquo Prozesse

bull Einfachere Programmierung (gegenuumlber Tasks) wenn mehrere gleichzeitige Aktivitaumlten von denen einige von Zeit zu Zeit blockieren modelliert werden muumlssen

bull Bessere Performance bei Erzeugung und Zerstoumlrung da keine Ressourcen mit Threads verbunden sind

bull Bessere Performance bei Mischung von CPU- mit IO-intensiven Aufgaben (kein Vorteil bei reiner CPU-Nutzung

bull ABER Da die Schutzfunktion der getrennten Adressraumlume fehlt werden Synchronisationsmechanismen benoumltigt

Seite 18

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselbull Zur Erinnerung

ndash Auf einem Rechner laufen mehrere Prozessendash Es gibt meist nur eine CPUndash Das heiszligt die Prozesse muumlssen sich in der Nutzung der CPU abwechselnndash Das Betriebssystem entscheidet welcher Prozess als naumlchstes die CPU benutzen

darfbull Komponenten des Scheduling

ndash Prozesswechselkostenndash Warteschlangenmodellendash Scheduling-Verfahren

Seite 19

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselkostenbull Ein Prozesswechsel zwischen 2 Prozessen A und B schlieszligt genau genommen drei

weitere mit einndash Prozess A Unterbrechungsbearbeitung (UB)ndash UB Betriebssystem (BS)ndash BS Prozess Bndash Prozess B BS

ndash BS Prozess A

BS

Unterbr

Prozess A

Prozess B

1 KW (Kontextwechsel)

2 KW

3 KW 4 KW

5 KW

Prozess A ist verdraumlngt

bull Beim Prozesswechsel muss der Kontext des Prozesses im PCB gesichert werden dh beim 1 PW save state into PCBA und reload state from PCBB

bull Prozesswechsel sind relativ teuer (zB 122 μs auf Sun Sparc 20) 2 Prozesswechsel1 Prozesswechsel

(PW)

Seite 20

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodellebull Prozesse werden intern in Warteschlangen gehalten wenn ihnen die angeforderten

Betriebsmittel (zB die CPU) nicht zur Verfuumlgung stehen oder die erwarteten Ereignisse (zB Beendigung eines Prozesses) noch nicht eingetreten sind

bull Die Auswahlstrategien der Warteschlangen haben wesentlichen Einfluss auf das Systemverhalten

bull Prozesse migrieren aus Sicht des Betriebssystems zwischen den verschiedenen Warteschlangen

ndash Job queue (Prozessliste) Menge aller Prozesse im Systemndash Ready queue (Bereitliste CPU-Warteschlange) Menge der Prozesse die im

Hauptspeicher geladen und bereit zur Ausfuumlhrung sindndash Device queues (Warteschlange fuumlr jedes Geraumlt) Menge der Prozesse die auf ein

IO-Geraumlt warten

Seite 21

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Prozesse migrieren zwischen den Warteschlangen

Seite 22

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Beispiel

Seite 23

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Seite 24

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Ankunftszeit Task wird in Taskliste aufgenommen

Anforderungszeit Ereignis tritt ein Task wird ablaufwilligStartzeit Task erhaumllt

erstmalig die CPU zugeteilt

Beendigungszeit Task hat Aufgabe erledigt und ruht wieder

Deadline Zeit zu der die Task spaumltestens beendet sein muss

Ausfuumlhrungszeit Rechenzeit der Task (ohne Wartezeiten)

Periode Zeitdifferenz zwischen aufeinander folgenden Anforderungen

Spielraum Restzeit zwischen Beendigung und Deadline

Reaktionszeit Zeit zwischen Anfor-derung und Start der Ausfuumlhrung

Seite 25

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

ai Ankunftszeit (Arrival Time) Zeitpunkt an dem eine Task dem Betriebssystem bekannt gemacht wird die Taskverwaltung nimmt die Task in die Taskliste und setzt sie in den Zustand ruhend

ri Anforderungszeit (Request Time) Die Task bewirbt sich bei der Taskverwaltung um den Prozessor

si Startzeit (Start Time) die Task erhaumllt den Prozessor zugeteilt

ci Beendigungszeit (Completion Time) Die Task hat ihre Aufgabe erledigt und kehrt in den Zustand ruhend zuruumlck

di Zeitschranke (Deadline) Zeitpunkt an dem die Taskausfuumlhrung spaumltestens beendet sein muss Die Zeitschranke kann hart fest oder weich sein

pi Periode (Period) Zeitdauer kennzeichnet die Wiederholungsrate bei periodischen Tasks sie ergibt sich aus der Zeitdifferenz zwischen zwei aufeinander folgenden Anforderungszeiten einer Task

ei Ausfuumlhrungszeit (Execution Time) Zeitdauer die eine Task zur Ausfuumlhrung ihrer Aufgabe benoumltigt wenn sie sich im Zustand laufend befindet Eine Variante ist die maximale Ausfuumlhrungszeit (worst case execution time = WCET) eine obere Schranke der Ausfuumlhrungszeit die in keinem Fall uumlberschritten werden darf

li Spielraum (Laxity) verbleibende Restzeit zwischen Beendigungszeit und Zeitschranke

ji Reaktionszeit (Reaction Time Release Jitter) Zeitraum kennzeichnet die Verzoumlgerung zwischen Anforderung und dem Start der Ausfuumlhrung

Seite 26

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Uumlbungsfragen (Vorl Uni Stuttgart)

1048709 Eine Task im Zustand ldquorunnablerdquo wird momentan ausgefuumlhrt

1048709 Ein Task-Zustand kann direkt von ldquorunningrdquo zu ldquodormantrdquo wechseln

1048709 Eine Task im Zustand ldquosuspendedrdquo kann direkt in den Zustand ldquorunningrdquo wechseln

1048709 Eine Task im Zustand ldquodormantrdquo ist nicht bereit da Zeit- oder andere Bedingungen nicht

erfuumlllt sind

1048709 Eine Task im Zustand ldquosuspendedrdquo wartet auf das Auftreten eines Events

Seite 9

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Erzeugen von Prozessen bull Prozesse werden erzeugt bei

ndash Initialisierung des Systems (einfache Systeme zB Steuerung eines Mikrowellenherds)

ndash Systemaufruf zum Erzeugen eines (Sohn-)Prozesses durch einen anderen (Vater-)Prozess

ndash Benutzeranfrage einen neuen Prozess zu erzeugenndash Initiierung einer Stapelverarbeitung (Batch-Job)

bull POSIX-Systeme benutzen hierzu den fork() Systemaufrufndash Der neu erzeugte Prozess (child) ist eine exakte Kopie des erzeugenden Prozesses (parent)

besitzt aber eine neue Prozessnummerndash Beide Prozesse fuumlhren dieselben Instruktionen nach dem fork() ausndash Der Ergebniswert des fork() Systemaufrufs ist in beiden Prozessen unterschiedlichndash Mittels des Systemaufrufs exec() koumlnnen in einem Prozess neue Programme gestartet

werden

bull Windows Systemaufruf CreateProcess()bull Da beliebige Prozesse neue Prozesse erzeugen koumlnnen entsteht eine Hierarchie

(Baum) von Prozessen die als verkettete Liste organisiert ist(POSIX = Portable Operating System Interface (Standard-Schnittstelle zw Applikation und Betriebssystem)

Seite 10

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Beenden von Prozessen bull Prozesse koumlnnen sich selbst durch den exit()-Systemaufruf beenden und damit aus

dem System entfernenbull Ein Prozess kann die von ihm erzeugten Prozesse beenden falls

ndash ein Prozess die ihm zugestandenen Betriebsmittel verbraucht hatndash ein Prozess nicht laumlnger gebraucht wird oder fallsndash der erzeugende Prozess sich beendet und es nicht gewuumlnscht oder erlaubt ist

dass die erzeugten Prozesse unabhaumlngig weiter existieren (cascading termination)bull Auf die Beendigung eines erzeugten Prozesses kann in POSIX-Systemen mit Hilfe des

wait() Systemaufrufs gewartet werdenbull Der Ergebniswert (return code) eines sich beendenden Prozesses wird an den

erzeugenden Prozess weitergeleitet

Seite 11

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

while (1) repeat forever type_prompt() display prompt on screen read_command() read input from the terminal

pid = fork() create a new

process if (pid lt 0) repeat if system call failed

perror(fork)continue

if (pid = 0) parent process

waitpid(pid ampstatus 0) wait for child

else child process execve(command params 0) execute

command

Beispiel einfacher Kommandointerpreter

als Sohnprozessals Vaterprozess

Seite 12

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Die 5 Taskzustaumlnde mit den wichtigsten Uumlbergaumlngen

dormant existent

ready bereit

running laufend terminated

beendet

suspended blockiert

Task ist der Prozessverwaltung bekannt gegeben

Task ist gestartet und alle Betriebsmittel vorhanden (eingeplant)

Betriebsmittel fehlen

Weitere Begriffe

Dormant = idle new

Existent = ruhend

Ready = runnable busy

Bereit = ablaufwillig rechenbereit

Running = executing

Laufend = ablaufend rechnend aktiv

Suspended = blocked waiting

Task ist abgearbeitet

Task ist eliminiert

Betriebsmittel vorhanden

Task ist der Prozessor zugeteilt

Task ist verdraumlngt

Seite 13

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Die 5 Taskzustaumlnde mit den wichtigsten Uumlbergaumlngen

dormant existent

ready bereit

running laufend terminated

beendet

suspended blockiert

admitted

IO or event wait

exit

Task ist eliminiert

IO or event completion

dispatch Interrupt trap

Seite 14

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Zustandsuumlbergaumlnge (Umhaumlngen in eine andere Liste) bull Es existieren drei Arten des Prozessor-Entzugs

ndash Aufgabe des Prozessors durch einen Warteaufruf Wartelistendash Verdraumlngung durch einen anderen Prozess (Praumlemption) Bereitlistendash Beendigung

bull Vom Zustand bdquoblockiertldquo geht es nicht direkt in den Zustand bdquorunningldquobull Der Uumlbergang von bdquorunningldquo nach bdquoblockiertldquo wird immer durch den Prozess selbst

initiiertbull Der Uumlbergang von bdquorunningldquo nach bdquobeendetldquo wird immer durch den Prozess selbst

initiiertbull Der Uumlbergang von bdquobereitldquo nach bdquorunningldquo und zuruumlck geschieht immer durch das

Betriebssystem

Seite 15

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Leichtgewichtsprozesse (Threads)bull Threads sind parallele Kontrollfluumlsse die nicht gegeneinander abgeschottet sind

ndash laufen innerhalb des Adressraums eines bdquoechtenldquo Rechenprozessesndash teilen sich gemeinsame Ressourcen (zB globale Variable)

bull Es gibt Threads im Betriebssystem-Kernel Scheduling durch BSbull Es gibt Threads im Usermodus des Betriebssystems Scheduling durch Anwendung

BS nur fuumlr Prozess-Scheduling verantwortlich

Kernel

Usermodus

Prozess

Thread

Seite 16

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Unterschiede zwischen Tasks und Threads

bull Aus Sicht der Betriebszustaumlnde der Zeitparameter des Schedulings und der Synchronisation sind Thread und Task gleich

Task Thread

Besitzer von Betriebsmitteln Kann auszliger Prozessor selbst keine Betriebsmittel besitzen verfuumlgt aber uumlber alle Betriebsmittel der Task der er angehoumlrt

Eigener Adressraum Adressraum der Task der er angehoumlrt Threads haben einen gemeinsamen Adressraum

Enthaumllt einen oder mehrere Tasks Element einer Task

Kommunikation uumlber Taskgrenzen hinaus bevorzugt uumlber Botschaften

Kommunikation zwischen den Threads bevorzugt uumlber gleiche Daten

Task wird charakterisiert uumlber einen PCB

Thread wird charakterisiert uumlber Programmzaumlhler Register Stack und Zustand

Seite 17

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Vorteile von Threadsbull Kontextwechsel zwischen Threads effizienter als zwischen Prozessen

ndash kein Wechsel des Adressraumsndash kein automatisches Schedulingndash kein Retten und Restaurieren des Kontextes (nur Programmzaumlhler und Register)

bull Pro Zeiteinheit sind viel mehr Threadwechsel als Prozesswechsel moumlglich deshalb auch bdquoleichtgewichtigeldquo Prozesse

bull Einfachere Programmierung (gegenuumlber Tasks) wenn mehrere gleichzeitige Aktivitaumlten von denen einige von Zeit zu Zeit blockieren modelliert werden muumlssen

bull Bessere Performance bei Erzeugung und Zerstoumlrung da keine Ressourcen mit Threads verbunden sind

bull Bessere Performance bei Mischung von CPU- mit IO-intensiven Aufgaben (kein Vorteil bei reiner CPU-Nutzung

bull ABER Da die Schutzfunktion der getrennten Adressraumlume fehlt werden Synchronisationsmechanismen benoumltigt

Seite 18

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselbull Zur Erinnerung

ndash Auf einem Rechner laufen mehrere Prozessendash Es gibt meist nur eine CPUndash Das heiszligt die Prozesse muumlssen sich in der Nutzung der CPU abwechselnndash Das Betriebssystem entscheidet welcher Prozess als naumlchstes die CPU benutzen

darfbull Komponenten des Scheduling

ndash Prozesswechselkostenndash Warteschlangenmodellendash Scheduling-Verfahren

Seite 19

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselkostenbull Ein Prozesswechsel zwischen 2 Prozessen A und B schlieszligt genau genommen drei

weitere mit einndash Prozess A Unterbrechungsbearbeitung (UB)ndash UB Betriebssystem (BS)ndash BS Prozess Bndash Prozess B BS

ndash BS Prozess A

BS

Unterbr

Prozess A

Prozess B

1 KW (Kontextwechsel)

2 KW

3 KW 4 KW

5 KW

Prozess A ist verdraumlngt

bull Beim Prozesswechsel muss der Kontext des Prozesses im PCB gesichert werden dh beim 1 PW save state into PCBA und reload state from PCBB

bull Prozesswechsel sind relativ teuer (zB 122 μs auf Sun Sparc 20) 2 Prozesswechsel1 Prozesswechsel

(PW)

Seite 20

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodellebull Prozesse werden intern in Warteschlangen gehalten wenn ihnen die angeforderten

Betriebsmittel (zB die CPU) nicht zur Verfuumlgung stehen oder die erwarteten Ereignisse (zB Beendigung eines Prozesses) noch nicht eingetreten sind

bull Die Auswahlstrategien der Warteschlangen haben wesentlichen Einfluss auf das Systemverhalten

bull Prozesse migrieren aus Sicht des Betriebssystems zwischen den verschiedenen Warteschlangen

ndash Job queue (Prozessliste) Menge aller Prozesse im Systemndash Ready queue (Bereitliste CPU-Warteschlange) Menge der Prozesse die im

Hauptspeicher geladen und bereit zur Ausfuumlhrung sindndash Device queues (Warteschlange fuumlr jedes Geraumlt) Menge der Prozesse die auf ein

IO-Geraumlt warten

Seite 21

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Prozesse migrieren zwischen den Warteschlangen

Seite 22

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Beispiel

Seite 23

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Seite 24

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Ankunftszeit Task wird in Taskliste aufgenommen

Anforderungszeit Ereignis tritt ein Task wird ablaufwilligStartzeit Task erhaumllt

erstmalig die CPU zugeteilt

Beendigungszeit Task hat Aufgabe erledigt und ruht wieder

Deadline Zeit zu der die Task spaumltestens beendet sein muss

Ausfuumlhrungszeit Rechenzeit der Task (ohne Wartezeiten)

Periode Zeitdifferenz zwischen aufeinander folgenden Anforderungen

Spielraum Restzeit zwischen Beendigung und Deadline

Reaktionszeit Zeit zwischen Anfor-derung und Start der Ausfuumlhrung

Seite 25

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

ai Ankunftszeit (Arrival Time) Zeitpunkt an dem eine Task dem Betriebssystem bekannt gemacht wird die Taskverwaltung nimmt die Task in die Taskliste und setzt sie in den Zustand ruhend

ri Anforderungszeit (Request Time) Die Task bewirbt sich bei der Taskverwaltung um den Prozessor

si Startzeit (Start Time) die Task erhaumllt den Prozessor zugeteilt

ci Beendigungszeit (Completion Time) Die Task hat ihre Aufgabe erledigt und kehrt in den Zustand ruhend zuruumlck

di Zeitschranke (Deadline) Zeitpunkt an dem die Taskausfuumlhrung spaumltestens beendet sein muss Die Zeitschranke kann hart fest oder weich sein

pi Periode (Period) Zeitdauer kennzeichnet die Wiederholungsrate bei periodischen Tasks sie ergibt sich aus der Zeitdifferenz zwischen zwei aufeinander folgenden Anforderungszeiten einer Task

ei Ausfuumlhrungszeit (Execution Time) Zeitdauer die eine Task zur Ausfuumlhrung ihrer Aufgabe benoumltigt wenn sie sich im Zustand laufend befindet Eine Variante ist die maximale Ausfuumlhrungszeit (worst case execution time = WCET) eine obere Schranke der Ausfuumlhrungszeit die in keinem Fall uumlberschritten werden darf

li Spielraum (Laxity) verbleibende Restzeit zwischen Beendigungszeit und Zeitschranke

ji Reaktionszeit (Reaction Time Release Jitter) Zeitraum kennzeichnet die Verzoumlgerung zwischen Anforderung und dem Start der Ausfuumlhrung

Seite 26

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Uumlbungsfragen (Vorl Uni Stuttgart)

1048709 Eine Task im Zustand ldquorunnablerdquo wird momentan ausgefuumlhrt

1048709 Ein Task-Zustand kann direkt von ldquorunningrdquo zu ldquodormantrdquo wechseln

1048709 Eine Task im Zustand ldquosuspendedrdquo kann direkt in den Zustand ldquorunningrdquo wechseln

1048709 Eine Task im Zustand ldquodormantrdquo ist nicht bereit da Zeit- oder andere Bedingungen nicht

erfuumlllt sind

1048709 Eine Task im Zustand ldquosuspendedrdquo wartet auf das Auftreten eines Events

Seite 10

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Beenden von Prozessen bull Prozesse koumlnnen sich selbst durch den exit()-Systemaufruf beenden und damit aus

dem System entfernenbull Ein Prozess kann die von ihm erzeugten Prozesse beenden falls

ndash ein Prozess die ihm zugestandenen Betriebsmittel verbraucht hatndash ein Prozess nicht laumlnger gebraucht wird oder fallsndash der erzeugende Prozess sich beendet und es nicht gewuumlnscht oder erlaubt ist

dass die erzeugten Prozesse unabhaumlngig weiter existieren (cascading termination)bull Auf die Beendigung eines erzeugten Prozesses kann in POSIX-Systemen mit Hilfe des

wait() Systemaufrufs gewartet werdenbull Der Ergebniswert (return code) eines sich beendenden Prozesses wird an den

erzeugenden Prozess weitergeleitet

Seite 11

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

while (1) repeat forever type_prompt() display prompt on screen read_command() read input from the terminal

pid = fork() create a new

process if (pid lt 0) repeat if system call failed

perror(fork)continue

if (pid = 0) parent process

waitpid(pid ampstatus 0) wait for child

else child process execve(command params 0) execute

command

Beispiel einfacher Kommandointerpreter

als Sohnprozessals Vaterprozess

Seite 12

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Die 5 Taskzustaumlnde mit den wichtigsten Uumlbergaumlngen

dormant existent

ready bereit

running laufend terminated

beendet

suspended blockiert

Task ist der Prozessverwaltung bekannt gegeben

Task ist gestartet und alle Betriebsmittel vorhanden (eingeplant)

Betriebsmittel fehlen

Weitere Begriffe

Dormant = idle new

Existent = ruhend

Ready = runnable busy

Bereit = ablaufwillig rechenbereit

Running = executing

Laufend = ablaufend rechnend aktiv

Suspended = blocked waiting

Task ist abgearbeitet

Task ist eliminiert

Betriebsmittel vorhanden

Task ist der Prozessor zugeteilt

Task ist verdraumlngt

Seite 13

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Die 5 Taskzustaumlnde mit den wichtigsten Uumlbergaumlngen

dormant existent

ready bereit

running laufend terminated

beendet

suspended blockiert

admitted

IO or event wait

exit

Task ist eliminiert

IO or event completion

dispatch Interrupt trap

Seite 14

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Zustandsuumlbergaumlnge (Umhaumlngen in eine andere Liste) bull Es existieren drei Arten des Prozessor-Entzugs

ndash Aufgabe des Prozessors durch einen Warteaufruf Wartelistendash Verdraumlngung durch einen anderen Prozess (Praumlemption) Bereitlistendash Beendigung

bull Vom Zustand bdquoblockiertldquo geht es nicht direkt in den Zustand bdquorunningldquobull Der Uumlbergang von bdquorunningldquo nach bdquoblockiertldquo wird immer durch den Prozess selbst

initiiertbull Der Uumlbergang von bdquorunningldquo nach bdquobeendetldquo wird immer durch den Prozess selbst

initiiertbull Der Uumlbergang von bdquobereitldquo nach bdquorunningldquo und zuruumlck geschieht immer durch das

Betriebssystem

Seite 15

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Leichtgewichtsprozesse (Threads)bull Threads sind parallele Kontrollfluumlsse die nicht gegeneinander abgeschottet sind

ndash laufen innerhalb des Adressraums eines bdquoechtenldquo Rechenprozessesndash teilen sich gemeinsame Ressourcen (zB globale Variable)

bull Es gibt Threads im Betriebssystem-Kernel Scheduling durch BSbull Es gibt Threads im Usermodus des Betriebssystems Scheduling durch Anwendung

BS nur fuumlr Prozess-Scheduling verantwortlich

Kernel

Usermodus

Prozess

Thread

Seite 16

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Unterschiede zwischen Tasks und Threads

bull Aus Sicht der Betriebszustaumlnde der Zeitparameter des Schedulings und der Synchronisation sind Thread und Task gleich

Task Thread

Besitzer von Betriebsmitteln Kann auszliger Prozessor selbst keine Betriebsmittel besitzen verfuumlgt aber uumlber alle Betriebsmittel der Task der er angehoumlrt

Eigener Adressraum Adressraum der Task der er angehoumlrt Threads haben einen gemeinsamen Adressraum

Enthaumllt einen oder mehrere Tasks Element einer Task

Kommunikation uumlber Taskgrenzen hinaus bevorzugt uumlber Botschaften

Kommunikation zwischen den Threads bevorzugt uumlber gleiche Daten

Task wird charakterisiert uumlber einen PCB

Thread wird charakterisiert uumlber Programmzaumlhler Register Stack und Zustand

Seite 17

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Vorteile von Threadsbull Kontextwechsel zwischen Threads effizienter als zwischen Prozessen

ndash kein Wechsel des Adressraumsndash kein automatisches Schedulingndash kein Retten und Restaurieren des Kontextes (nur Programmzaumlhler und Register)

bull Pro Zeiteinheit sind viel mehr Threadwechsel als Prozesswechsel moumlglich deshalb auch bdquoleichtgewichtigeldquo Prozesse

bull Einfachere Programmierung (gegenuumlber Tasks) wenn mehrere gleichzeitige Aktivitaumlten von denen einige von Zeit zu Zeit blockieren modelliert werden muumlssen

bull Bessere Performance bei Erzeugung und Zerstoumlrung da keine Ressourcen mit Threads verbunden sind

bull Bessere Performance bei Mischung von CPU- mit IO-intensiven Aufgaben (kein Vorteil bei reiner CPU-Nutzung

bull ABER Da die Schutzfunktion der getrennten Adressraumlume fehlt werden Synchronisationsmechanismen benoumltigt

Seite 18

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselbull Zur Erinnerung

ndash Auf einem Rechner laufen mehrere Prozessendash Es gibt meist nur eine CPUndash Das heiszligt die Prozesse muumlssen sich in der Nutzung der CPU abwechselnndash Das Betriebssystem entscheidet welcher Prozess als naumlchstes die CPU benutzen

darfbull Komponenten des Scheduling

ndash Prozesswechselkostenndash Warteschlangenmodellendash Scheduling-Verfahren

Seite 19

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselkostenbull Ein Prozesswechsel zwischen 2 Prozessen A und B schlieszligt genau genommen drei

weitere mit einndash Prozess A Unterbrechungsbearbeitung (UB)ndash UB Betriebssystem (BS)ndash BS Prozess Bndash Prozess B BS

ndash BS Prozess A

BS

Unterbr

Prozess A

Prozess B

1 KW (Kontextwechsel)

2 KW

3 KW 4 KW

5 KW

Prozess A ist verdraumlngt

bull Beim Prozesswechsel muss der Kontext des Prozesses im PCB gesichert werden dh beim 1 PW save state into PCBA und reload state from PCBB

bull Prozesswechsel sind relativ teuer (zB 122 μs auf Sun Sparc 20) 2 Prozesswechsel1 Prozesswechsel

(PW)

Seite 20

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodellebull Prozesse werden intern in Warteschlangen gehalten wenn ihnen die angeforderten

Betriebsmittel (zB die CPU) nicht zur Verfuumlgung stehen oder die erwarteten Ereignisse (zB Beendigung eines Prozesses) noch nicht eingetreten sind

bull Die Auswahlstrategien der Warteschlangen haben wesentlichen Einfluss auf das Systemverhalten

bull Prozesse migrieren aus Sicht des Betriebssystems zwischen den verschiedenen Warteschlangen

ndash Job queue (Prozessliste) Menge aller Prozesse im Systemndash Ready queue (Bereitliste CPU-Warteschlange) Menge der Prozesse die im

Hauptspeicher geladen und bereit zur Ausfuumlhrung sindndash Device queues (Warteschlange fuumlr jedes Geraumlt) Menge der Prozesse die auf ein

IO-Geraumlt warten

Seite 21

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Prozesse migrieren zwischen den Warteschlangen

Seite 22

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Beispiel

Seite 23

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Seite 24

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Ankunftszeit Task wird in Taskliste aufgenommen

Anforderungszeit Ereignis tritt ein Task wird ablaufwilligStartzeit Task erhaumllt

erstmalig die CPU zugeteilt

Beendigungszeit Task hat Aufgabe erledigt und ruht wieder

Deadline Zeit zu der die Task spaumltestens beendet sein muss

Ausfuumlhrungszeit Rechenzeit der Task (ohne Wartezeiten)

Periode Zeitdifferenz zwischen aufeinander folgenden Anforderungen

Spielraum Restzeit zwischen Beendigung und Deadline

Reaktionszeit Zeit zwischen Anfor-derung und Start der Ausfuumlhrung

Seite 25

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

ai Ankunftszeit (Arrival Time) Zeitpunkt an dem eine Task dem Betriebssystem bekannt gemacht wird die Taskverwaltung nimmt die Task in die Taskliste und setzt sie in den Zustand ruhend

ri Anforderungszeit (Request Time) Die Task bewirbt sich bei der Taskverwaltung um den Prozessor

si Startzeit (Start Time) die Task erhaumllt den Prozessor zugeteilt

ci Beendigungszeit (Completion Time) Die Task hat ihre Aufgabe erledigt und kehrt in den Zustand ruhend zuruumlck

di Zeitschranke (Deadline) Zeitpunkt an dem die Taskausfuumlhrung spaumltestens beendet sein muss Die Zeitschranke kann hart fest oder weich sein

pi Periode (Period) Zeitdauer kennzeichnet die Wiederholungsrate bei periodischen Tasks sie ergibt sich aus der Zeitdifferenz zwischen zwei aufeinander folgenden Anforderungszeiten einer Task

ei Ausfuumlhrungszeit (Execution Time) Zeitdauer die eine Task zur Ausfuumlhrung ihrer Aufgabe benoumltigt wenn sie sich im Zustand laufend befindet Eine Variante ist die maximale Ausfuumlhrungszeit (worst case execution time = WCET) eine obere Schranke der Ausfuumlhrungszeit die in keinem Fall uumlberschritten werden darf

li Spielraum (Laxity) verbleibende Restzeit zwischen Beendigungszeit und Zeitschranke

ji Reaktionszeit (Reaction Time Release Jitter) Zeitraum kennzeichnet die Verzoumlgerung zwischen Anforderung und dem Start der Ausfuumlhrung

Seite 26

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Uumlbungsfragen (Vorl Uni Stuttgart)

1048709 Eine Task im Zustand ldquorunnablerdquo wird momentan ausgefuumlhrt

1048709 Ein Task-Zustand kann direkt von ldquorunningrdquo zu ldquodormantrdquo wechseln

1048709 Eine Task im Zustand ldquosuspendedrdquo kann direkt in den Zustand ldquorunningrdquo wechseln

1048709 Eine Task im Zustand ldquodormantrdquo ist nicht bereit da Zeit- oder andere Bedingungen nicht

erfuumlllt sind

1048709 Eine Task im Zustand ldquosuspendedrdquo wartet auf das Auftreten eines Events

Seite 11

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

while (1) repeat forever type_prompt() display prompt on screen read_command() read input from the terminal

pid = fork() create a new

process if (pid lt 0) repeat if system call failed

perror(fork)continue

if (pid = 0) parent process

waitpid(pid ampstatus 0) wait for child

else child process execve(command params 0) execute

command

Beispiel einfacher Kommandointerpreter

als Sohnprozessals Vaterprozess

Seite 12

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Die 5 Taskzustaumlnde mit den wichtigsten Uumlbergaumlngen

dormant existent

ready bereit

running laufend terminated

beendet

suspended blockiert

Task ist der Prozessverwaltung bekannt gegeben

Task ist gestartet und alle Betriebsmittel vorhanden (eingeplant)

Betriebsmittel fehlen

Weitere Begriffe

Dormant = idle new

Existent = ruhend

Ready = runnable busy

Bereit = ablaufwillig rechenbereit

Running = executing

Laufend = ablaufend rechnend aktiv

Suspended = blocked waiting

Task ist abgearbeitet

Task ist eliminiert

Betriebsmittel vorhanden

Task ist der Prozessor zugeteilt

Task ist verdraumlngt

Seite 13

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Die 5 Taskzustaumlnde mit den wichtigsten Uumlbergaumlngen

dormant existent

ready bereit

running laufend terminated

beendet

suspended blockiert

admitted

IO or event wait

exit

Task ist eliminiert

IO or event completion

dispatch Interrupt trap

Seite 14

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Zustandsuumlbergaumlnge (Umhaumlngen in eine andere Liste) bull Es existieren drei Arten des Prozessor-Entzugs

ndash Aufgabe des Prozessors durch einen Warteaufruf Wartelistendash Verdraumlngung durch einen anderen Prozess (Praumlemption) Bereitlistendash Beendigung

bull Vom Zustand bdquoblockiertldquo geht es nicht direkt in den Zustand bdquorunningldquobull Der Uumlbergang von bdquorunningldquo nach bdquoblockiertldquo wird immer durch den Prozess selbst

initiiertbull Der Uumlbergang von bdquorunningldquo nach bdquobeendetldquo wird immer durch den Prozess selbst

initiiertbull Der Uumlbergang von bdquobereitldquo nach bdquorunningldquo und zuruumlck geschieht immer durch das

Betriebssystem

Seite 15

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Leichtgewichtsprozesse (Threads)bull Threads sind parallele Kontrollfluumlsse die nicht gegeneinander abgeschottet sind

ndash laufen innerhalb des Adressraums eines bdquoechtenldquo Rechenprozessesndash teilen sich gemeinsame Ressourcen (zB globale Variable)

bull Es gibt Threads im Betriebssystem-Kernel Scheduling durch BSbull Es gibt Threads im Usermodus des Betriebssystems Scheduling durch Anwendung

BS nur fuumlr Prozess-Scheduling verantwortlich

Kernel

Usermodus

Prozess

Thread

Seite 16

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Unterschiede zwischen Tasks und Threads

bull Aus Sicht der Betriebszustaumlnde der Zeitparameter des Schedulings und der Synchronisation sind Thread und Task gleich

Task Thread

Besitzer von Betriebsmitteln Kann auszliger Prozessor selbst keine Betriebsmittel besitzen verfuumlgt aber uumlber alle Betriebsmittel der Task der er angehoumlrt

Eigener Adressraum Adressraum der Task der er angehoumlrt Threads haben einen gemeinsamen Adressraum

Enthaumllt einen oder mehrere Tasks Element einer Task

Kommunikation uumlber Taskgrenzen hinaus bevorzugt uumlber Botschaften

Kommunikation zwischen den Threads bevorzugt uumlber gleiche Daten

Task wird charakterisiert uumlber einen PCB

Thread wird charakterisiert uumlber Programmzaumlhler Register Stack und Zustand

Seite 17

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Vorteile von Threadsbull Kontextwechsel zwischen Threads effizienter als zwischen Prozessen

ndash kein Wechsel des Adressraumsndash kein automatisches Schedulingndash kein Retten und Restaurieren des Kontextes (nur Programmzaumlhler und Register)

bull Pro Zeiteinheit sind viel mehr Threadwechsel als Prozesswechsel moumlglich deshalb auch bdquoleichtgewichtigeldquo Prozesse

bull Einfachere Programmierung (gegenuumlber Tasks) wenn mehrere gleichzeitige Aktivitaumlten von denen einige von Zeit zu Zeit blockieren modelliert werden muumlssen

bull Bessere Performance bei Erzeugung und Zerstoumlrung da keine Ressourcen mit Threads verbunden sind

bull Bessere Performance bei Mischung von CPU- mit IO-intensiven Aufgaben (kein Vorteil bei reiner CPU-Nutzung

bull ABER Da die Schutzfunktion der getrennten Adressraumlume fehlt werden Synchronisationsmechanismen benoumltigt

Seite 18

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselbull Zur Erinnerung

ndash Auf einem Rechner laufen mehrere Prozessendash Es gibt meist nur eine CPUndash Das heiszligt die Prozesse muumlssen sich in der Nutzung der CPU abwechselnndash Das Betriebssystem entscheidet welcher Prozess als naumlchstes die CPU benutzen

darfbull Komponenten des Scheduling

ndash Prozesswechselkostenndash Warteschlangenmodellendash Scheduling-Verfahren

Seite 19

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselkostenbull Ein Prozesswechsel zwischen 2 Prozessen A und B schlieszligt genau genommen drei

weitere mit einndash Prozess A Unterbrechungsbearbeitung (UB)ndash UB Betriebssystem (BS)ndash BS Prozess Bndash Prozess B BS

ndash BS Prozess A

BS

Unterbr

Prozess A

Prozess B

1 KW (Kontextwechsel)

2 KW

3 KW 4 KW

5 KW

Prozess A ist verdraumlngt

bull Beim Prozesswechsel muss der Kontext des Prozesses im PCB gesichert werden dh beim 1 PW save state into PCBA und reload state from PCBB

bull Prozesswechsel sind relativ teuer (zB 122 μs auf Sun Sparc 20) 2 Prozesswechsel1 Prozesswechsel

(PW)

Seite 20

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodellebull Prozesse werden intern in Warteschlangen gehalten wenn ihnen die angeforderten

Betriebsmittel (zB die CPU) nicht zur Verfuumlgung stehen oder die erwarteten Ereignisse (zB Beendigung eines Prozesses) noch nicht eingetreten sind

bull Die Auswahlstrategien der Warteschlangen haben wesentlichen Einfluss auf das Systemverhalten

bull Prozesse migrieren aus Sicht des Betriebssystems zwischen den verschiedenen Warteschlangen

ndash Job queue (Prozessliste) Menge aller Prozesse im Systemndash Ready queue (Bereitliste CPU-Warteschlange) Menge der Prozesse die im

Hauptspeicher geladen und bereit zur Ausfuumlhrung sindndash Device queues (Warteschlange fuumlr jedes Geraumlt) Menge der Prozesse die auf ein

IO-Geraumlt warten

Seite 21

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Prozesse migrieren zwischen den Warteschlangen

Seite 22

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Beispiel

Seite 23

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Seite 24

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Ankunftszeit Task wird in Taskliste aufgenommen

Anforderungszeit Ereignis tritt ein Task wird ablaufwilligStartzeit Task erhaumllt

erstmalig die CPU zugeteilt

Beendigungszeit Task hat Aufgabe erledigt und ruht wieder

Deadline Zeit zu der die Task spaumltestens beendet sein muss

Ausfuumlhrungszeit Rechenzeit der Task (ohne Wartezeiten)

Periode Zeitdifferenz zwischen aufeinander folgenden Anforderungen

Spielraum Restzeit zwischen Beendigung und Deadline

Reaktionszeit Zeit zwischen Anfor-derung und Start der Ausfuumlhrung

Seite 25

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

ai Ankunftszeit (Arrival Time) Zeitpunkt an dem eine Task dem Betriebssystem bekannt gemacht wird die Taskverwaltung nimmt die Task in die Taskliste und setzt sie in den Zustand ruhend

ri Anforderungszeit (Request Time) Die Task bewirbt sich bei der Taskverwaltung um den Prozessor

si Startzeit (Start Time) die Task erhaumllt den Prozessor zugeteilt

ci Beendigungszeit (Completion Time) Die Task hat ihre Aufgabe erledigt und kehrt in den Zustand ruhend zuruumlck

di Zeitschranke (Deadline) Zeitpunkt an dem die Taskausfuumlhrung spaumltestens beendet sein muss Die Zeitschranke kann hart fest oder weich sein

pi Periode (Period) Zeitdauer kennzeichnet die Wiederholungsrate bei periodischen Tasks sie ergibt sich aus der Zeitdifferenz zwischen zwei aufeinander folgenden Anforderungszeiten einer Task

ei Ausfuumlhrungszeit (Execution Time) Zeitdauer die eine Task zur Ausfuumlhrung ihrer Aufgabe benoumltigt wenn sie sich im Zustand laufend befindet Eine Variante ist die maximale Ausfuumlhrungszeit (worst case execution time = WCET) eine obere Schranke der Ausfuumlhrungszeit die in keinem Fall uumlberschritten werden darf

li Spielraum (Laxity) verbleibende Restzeit zwischen Beendigungszeit und Zeitschranke

ji Reaktionszeit (Reaction Time Release Jitter) Zeitraum kennzeichnet die Verzoumlgerung zwischen Anforderung und dem Start der Ausfuumlhrung

Seite 26

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Uumlbungsfragen (Vorl Uni Stuttgart)

1048709 Eine Task im Zustand ldquorunnablerdquo wird momentan ausgefuumlhrt

1048709 Ein Task-Zustand kann direkt von ldquorunningrdquo zu ldquodormantrdquo wechseln

1048709 Eine Task im Zustand ldquosuspendedrdquo kann direkt in den Zustand ldquorunningrdquo wechseln

1048709 Eine Task im Zustand ldquodormantrdquo ist nicht bereit da Zeit- oder andere Bedingungen nicht

erfuumlllt sind

1048709 Eine Task im Zustand ldquosuspendedrdquo wartet auf das Auftreten eines Events

Seite 12

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Die 5 Taskzustaumlnde mit den wichtigsten Uumlbergaumlngen

dormant existent

ready bereit

running laufend terminated

beendet

suspended blockiert

Task ist der Prozessverwaltung bekannt gegeben

Task ist gestartet und alle Betriebsmittel vorhanden (eingeplant)

Betriebsmittel fehlen

Weitere Begriffe

Dormant = idle new

Existent = ruhend

Ready = runnable busy

Bereit = ablaufwillig rechenbereit

Running = executing

Laufend = ablaufend rechnend aktiv

Suspended = blocked waiting

Task ist abgearbeitet

Task ist eliminiert

Betriebsmittel vorhanden

Task ist der Prozessor zugeteilt

Task ist verdraumlngt

Seite 13

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Die 5 Taskzustaumlnde mit den wichtigsten Uumlbergaumlngen

dormant existent

ready bereit

running laufend terminated

beendet

suspended blockiert

admitted

IO or event wait

exit

Task ist eliminiert

IO or event completion

dispatch Interrupt trap

Seite 14

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Zustandsuumlbergaumlnge (Umhaumlngen in eine andere Liste) bull Es existieren drei Arten des Prozessor-Entzugs

ndash Aufgabe des Prozessors durch einen Warteaufruf Wartelistendash Verdraumlngung durch einen anderen Prozess (Praumlemption) Bereitlistendash Beendigung

bull Vom Zustand bdquoblockiertldquo geht es nicht direkt in den Zustand bdquorunningldquobull Der Uumlbergang von bdquorunningldquo nach bdquoblockiertldquo wird immer durch den Prozess selbst

initiiertbull Der Uumlbergang von bdquorunningldquo nach bdquobeendetldquo wird immer durch den Prozess selbst

initiiertbull Der Uumlbergang von bdquobereitldquo nach bdquorunningldquo und zuruumlck geschieht immer durch das

Betriebssystem

Seite 15

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Leichtgewichtsprozesse (Threads)bull Threads sind parallele Kontrollfluumlsse die nicht gegeneinander abgeschottet sind

ndash laufen innerhalb des Adressraums eines bdquoechtenldquo Rechenprozessesndash teilen sich gemeinsame Ressourcen (zB globale Variable)

bull Es gibt Threads im Betriebssystem-Kernel Scheduling durch BSbull Es gibt Threads im Usermodus des Betriebssystems Scheduling durch Anwendung

BS nur fuumlr Prozess-Scheduling verantwortlich

Kernel

Usermodus

Prozess

Thread

Seite 16

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Unterschiede zwischen Tasks und Threads

bull Aus Sicht der Betriebszustaumlnde der Zeitparameter des Schedulings und der Synchronisation sind Thread und Task gleich

Task Thread

Besitzer von Betriebsmitteln Kann auszliger Prozessor selbst keine Betriebsmittel besitzen verfuumlgt aber uumlber alle Betriebsmittel der Task der er angehoumlrt

Eigener Adressraum Adressraum der Task der er angehoumlrt Threads haben einen gemeinsamen Adressraum

Enthaumllt einen oder mehrere Tasks Element einer Task

Kommunikation uumlber Taskgrenzen hinaus bevorzugt uumlber Botschaften

Kommunikation zwischen den Threads bevorzugt uumlber gleiche Daten

Task wird charakterisiert uumlber einen PCB

Thread wird charakterisiert uumlber Programmzaumlhler Register Stack und Zustand

Seite 17

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Vorteile von Threadsbull Kontextwechsel zwischen Threads effizienter als zwischen Prozessen

ndash kein Wechsel des Adressraumsndash kein automatisches Schedulingndash kein Retten und Restaurieren des Kontextes (nur Programmzaumlhler und Register)

bull Pro Zeiteinheit sind viel mehr Threadwechsel als Prozesswechsel moumlglich deshalb auch bdquoleichtgewichtigeldquo Prozesse

bull Einfachere Programmierung (gegenuumlber Tasks) wenn mehrere gleichzeitige Aktivitaumlten von denen einige von Zeit zu Zeit blockieren modelliert werden muumlssen

bull Bessere Performance bei Erzeugung und Zerstoumlrung da keine Ressourcen mit Threads verbunden sind

bull Bessere Performance bei Mischung von CPU- mit IO-intensiven Aufgaben (kein Vorteil bei reiner CPU-Nutzung

bull ABER Da die Schutzfunktion der getrennten Adressraumlume fehlt werden Synchronisationsmechanismen benoumltigt

Seite 18

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselbull Zur Erinnerung

ndash Auf einem Rechner laufen mehrere Prozessendash Es gibt meist nur eine CPUndash Das heiszligt die Prozesse muumlssen sich in der Nutzung der CPU abwechselnndash Das Betriebssystem entscheidet welcher Prozess als naumlchstes die CPU benutzen

darfbull Komponenten des Scheduling

ndash Prozesswechselkostenndash Warteschlangenmodellendash Scheduling-Verfahren

Seite 19

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselkostenbull Ein Prozesswechsel zwischen 2 Prozessen A und B schlieszligt genau genommen drei

weitere mit einndash Prozess A Unterbrechungsbearbeitung (UB)ndash UB Betriebssystem (BS)ndash BS Prozess Bndash Prozess B BS

ndash BS Prozess A

BS

Unterbr

Prozess A

Prozess B

1 KW (Kontextwechsel)

2 KW

3 KW 4 KW

5 KW

Prozess A ist verdraumlngt

bull Beim Prozesswechsel muss der Kontext des Prozesses im PCB gesichert werden dh beim 1 PW save state into PCBA und reload state from PCBB

bull Prozesswechsel sind relativ teuer (zB 122 μs auf Sun Sparc 20) 2 Prozesswechsel1 Prozesswechsel

(PW)

Seite 20

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodellebull Prozesse werden intern in Warteschlangen gehalten wenn ihnen die angeforderten

Betriebsmittel (zB die CPU) nicht zur Verfuumlgung stehen oder die erwarteten Ereignisse (zB Beendigung eines Prozesses) noch nicht eingetreten sind

bull Die Auswahlstrategien der Warteschlangen haben wesentlichen Einfluss auf das Systemverhalten

bull Prozesse migrieren aus Sicht des Betriebssystems zwischen den verschiedenen Warteschlangen

ndash Job queue (Prozessliste) Menge aller Prozesse im Systemndash Ready queue (Bereitliste CPU-Warteschlange) Menge der Prozesse die im

Hauptspeicher geladen und bereit zur Ausfuumlhrung sindndash Device queues (Warteschlange fuumlr jedes Geraumlt) Menge der Prozesse die auf ein

IO-Geraumlt warten

Seite 21

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Prozesse migrieren zwischen den Warteschlangen

Seite 22

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Beispiel

Seite 23

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Seite 24

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Ankunftszeit Task wird in Taskliste aufgenommen

Anforderungszeit Ereignis tritt ein Task wird ablaufwilligStartzeit Task erhaumllt

erstmalig die CPU zugeteilt

Beendigungszeit Task hat Aufgabe erledigt und ruht wieder

Deadline Zeit zu der die Task spaumltestens beendet sein muss

Ausfuumlhrungszeit Rechenzeit der Task (ohne Wartezeiten)

Periode Zeitdifferenz zwischen aufeinander folgenden Anforderungen

Spielraum Restzeit zwischen Beendigung und Deadline

Reaktionszeit Zeit zwischen Anfor-derung und Start der Ausfuumlhrung

Seite 25

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

ai Ankunftszeit (Arrival Time) Zeitpunkt an dem eine Task dem Betriebssystem bekannt gemacht wird die Taskverwaltung nimmt die Task in die Taskliste und setzt sie in den Zustand ruhend

ri Anforderungszeit (Request Time) Die Task bewirbt sich bei der Taskverwaltung um den Prozessor

si Startzeit (Start Time) die Task erhaumllt den Prozessor zugeteilt

ci Beendigungszeit (Completion Time) Die Task hat ihre Aufgabe erledigt und kehrt in den Zustand ruhend zuruumlck

di Zeitschranke (Deadline) Zeitpunkt an dem die Taskausfuumlhrung spaumltestens beendet sein muss Die Zeitschranke kann hart fest oder weich sein

pi Periode (Period) Zeitdauer kennzeichnet die Wiederholungsrate bei periodischen Tasks sie ergibt sich aus der Zeitdifferenz zwischen zwei aufeinander folgenden Anforderungszeiten einer Task

ei Ausfuumlhrungszeit (Execution Time) Zeitdauer die eine Task zur Ausfuumlhrung ihrer Aufgabe benoumltigt wenn sie sich im Zustand laufend befindet Eine Variante ist die maximale Ausfuumlhrungszeit (worst case execution time = WCET) eine obere Schranke der Ausfuumlhrungszeit die in keinem Fall uumlberschritten werden darf

li Spielraum (Laxity) verbleibende Restzeit zwischen Beendigungszeit und Zeitschranke

ji Reaktionszeit (Reaction Time Release Jitter) Zeitraum kennzeichnet die Verzoumlgerung zwischen Anforderung und dem Start der Ausfuumlhrung

Seite 26

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Uumlbungsfragen (Vorl Uni Stuttgart)

1048709 Eine Task im Zustand ldquorunnablerdquo wird momentan ausgefuumlhrt

1048709 Ein Task-Zustand kann direkt von ldquorunningrdquo zu ldquodormantrdquo wechseln

1048709 Eine Task im Zustand ldquosuspendedrdquo kann direkt in den Zustand ldquorunningrdquo wechseln

1048709 Eine Task im Zustand ldquodormantrdquo ist nicht bereit da Zeit- oder andere Bedingungen nicht

erfuumlllt sind

1048709 Eine Task im Zustand ldquosuspendedrdquo wartet auf das Auftreten eines Events

Seite 13

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Die 5 Taskzustaumlnde mit den wichtigsten Uumlbergaumlngen

dormant existent

ready bereit

running laufend terminated

beendet

suspended blockiert

admitted

IO or event wait

exit

Task ist eliminiert

IO or event completion

dispatch Interrupt trap

Seite 14

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Zustandsuumlbergaumlnge (Umhaumlngen in eine andere Liste) bull Es existieren drei Arten des Prozessor-Entzugs

ndash Aufgabe des Prozessors durch einen Warteaufruf Wartelistendash Verdraumlngung durch einen anderen Prozess (Praumlemption) Bereitlistendash Beendigung

bull Vom Zustand bdquoblockiertldquo geht es nicht direkt in den Zustand bdquorunningldquobull Der Uumlbergang von bdquorunningldquo nach bdquoblockiertldquo wird immer durch den Prozess selbst

initiiertbull Der Uumlbergang von bdquorunningldquo nach bdquobeendetldquo wird immer durch den Prozess selbst

initiiertbull Der Uumlbergang von bdquobereitldquo nach bdquorunningldquo und zuruumlck geschieht immer durch das

Betriebssystem

Seite 15

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Leichtgewichtsprozesse (Threads)bull Threads sind parallele Kontrollfluumlsse die nicht gegeneinander abgeschottet sind

ndash laufen innerhalb des Adressraums eines bdquoechtenldquo Rechenprozessesndash teilen sich gemeinsame Ressourcen (zB globale Variable)

bull Es gibt Threads im Betriebssystem-Kernel Scheduling durch BSbull Es gibt Threads im Usermodus des Betriebssystems Scheduling durch Anwendung

BS nur fuumlr Prozess-Scheduling verantwortlich

Kernel

Usermodus

Prozess

Thread

Seite 16

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Unterschiede zwischen Tasks und Threads

bull Aus Sicht der Betriebszustaumlnde der Zeitparameter des Schedulings und der Synchronisation sind Thread und Task gleich

Task Thread

Besitzer von Betriebsmitteln Kann auszliger Prozessor selbst keine Betriebsmittel besitzen verfuumlgt aber uumlber alle Betriebsmittel der Task der er angehoumlrt

Eigener Adressraum Adressraum der Task der er angehoumlrt Threads haben einen gemeinsamen Adressraum

Enthaumllt einen oder mehrere Tasks Element einer Task

Kommunikation uumlber Taskgrenzen hinaus bevorzugt uumlber Botschaften

Kommunikation zwischen den Threads bevorzugt uumlber gleiche Daten

Task wird charakterisiert uumlber einen PCB

Thread wird charakterisiert uumlber Programmzaumlhler Register Stack und Zustand

Seite 17

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Vorteile von Threadsbull Kontextwechsel zwischen Threads effizienter als zwischen Prozessen

ndash kein Wechsel des Adressraumsndash kein automatisches Schedulingndash kein Retten und Restaurieren des Kontextes (nur Programmzaumlhler und Register)

bull Pro Zeiteinheit sind viel mehr Threadwechsel als Prozesswechsel moumlglich deshalb auch bdquoleichtgewichtigeldquo Prozesse

bull Einfachere Programmierung (gegenuumlber Tasks) wenn mehrere gleichzeitige Aktivitaumlten von denen einige von Zeit zu Zeit blockieren modelliert werden muumlssen

bull Bessere Performance bei Erzeugung und Zerstoumlrung da keine Ressourcen mit Threads verbunden sind

bull Bessere Performance bei Mischung von CPU- mit IO-intensiven Aufgaben (kein Vorteil bei reiner CPU-Nutzung

bull ABER Da die Schutzfunktion der getrennten Adressraumlume fehlt werden Synchronisationsmechanismen benoumltigt

Seite 18

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselbull Zur Erinnerung

ndash Auf einem Rechner laufen mehrere Prozessendash Es gibt meist nur eine CPUndash Das heiszligt die Prozesse muumlssen sich in der Nutzung der CPU abwechselnndash Das Betriebssystem entscheidet welcher Prozess als naumlchstes die CPU benutzen

darfbull Komponenten des Scheduling

ndash Prozesswechselkostenndash Warteschlangenmodellendash Scheduling-Verfahren

Seite 19

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselkostenbull Ein Prozesswechsel zwischen 2 Prozessen A und B schlieszligt genau genommen drei

weitere mit einndash Prozess A Unterbrechungsbearbeitung (UB)ndash UB Betriebssystem (BS)ndash BS Prozess Bndash Prozess B BS

ndash BS Prozess A

BS

Unterbr

Prozess A

Prozess B

1 KW (Kontextwechsel)

2 KW

3 KW 4 KW

5 KW

Prozess A ist verdraumlngt

bull Beim Prozesswechsel muss der Kontext des Prozesses im PCB gesichert werden dh beim 1 PW save state into PCBA und reload state from PCBB

bull Prozesswechsel sind relativ teuer (zB 122 μs auf Sun Sparc 20) 2 Prozesswechsel1 Prozesswechsel

(PW)

Seite 20

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodellebull Prozesse werden intern in Warteschlangen gehalten wenn ihnen die angeforderten

Betriebsmittel (zB die CPU) nicht zur Verfuumlgung stehen oder die erwarteten Ereignisse (zB Beendigung eines Prozesses) noch nicht eingetreten sind

bull Die Auswahlstrategien der Warteschlangen haben wesentlichen Einfluss auf das Systemverhalten

bull Prozesse migrieren aus Sicht des Betriebssystems zwischen den verschiedenen Warteschlangen

ndash Job queue (Prozessliste) Menge aller Prozesse im Systemndash Ready queue (Bereitliste CPU-Warteschlange) Menge der Prozesse die im

Hauptspeicher geladen und bereit zur Ausfuumlhrung sindndash Device queues (Warteschlange fuumlr jedes Geraumlt) Menge der Prozesse die auf ein

IO-Geraumlt warten

Seite 21

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Prozesse migrieren zwischen den Warteschlangen

Seite 22

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Beispiel

Seite 23

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Seite 24

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Ankunftszeit Task wird in Taskliste aufgenommen

Anforderungszeit Ereignis tritt ein Task wird ablaufwilligStartzeit Task erhaumllt

erstmalig die CPU zugeteilt

Beendigungszeit Task hat Aufgabe erledigt und ruht wieder

Deadline Zeit zu der die Task spaumltestens beendet sein muss

Ausfuumlhrungszeit Rechenzeit der Task (ohne Wartezeiten)

Periode Zeitdifferenz zwischen aufeinander folgenden Anforderungen

Spielraum Restzeit zwischen Beendigung und Deadline

Reaktionszeit Zeit zwischen Anfor-derung und Start der Ausfuumlhrung

Seite 25

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

ai Ankunftszeit (Arrival Time) Zeitpunkt an dem eine Task dem Betriebssystem bekannt gemacht wird die Taskverwaltung nimmt die Task in die Taskliste und setzt sie in den Zustand ruhend

ri Anforderungszeit (Request Time) Die Task bewirbt sich bei der Taskverwaltung um den Prozessor

si Startzeit (Start Time) die Task erhaumllt den Prozessor zugeteilt

ci Beendigungszeit (Completion Time) Die Task hat ihre Aufgabe erledigt und kehrt in den Zustand ruhend zuruumlck

di Zeitschranke (Deadline) Zeitpunkt an dem die Taskausfuumlhrung spaumltestens beendet sein muss Die Zeitschranke kann hart fest oder weich sein

pi Periode (Period) Zeitdauer kennzeichnet die Wiederholungsrate bei periodischen Tasks sie ergibt sich aus der Zeitdifferenz zwischen zwei aufeinander folgenden Anforderungszeiten einer Task

ei Ausfuumlhrungszeit (Execution Time) Zeitdauer die eine Task zur Ausfuumlhrung ihrer Aufgabe benoumltigt wenn sie sich im Zustand laufend befindet Eine Variante ist die maximale Ausfuumlhrungszeit (worst case execution time = WCET) eine obere Schranke der Ausfuumlhrungszeit die in keinem Fall uumlberschritten werden darf

li Spielraum (Laxity) verbleibende Restzeit zwischen Beendigungszeit und Zeitschranke

ji Reaktionszeit (Reaction Time Release Jitter) Zeitraum kennzeichnet die Verzoumlgerung zwischen Anforderung und dem Start der Ausfuumlhrung

Seite 26

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Uumlbungsfragen (Vorl Uni Stuttgart)

1048709 Eine Task im Zustand ldquorunnablerdquo wird momentan ausgefuumlhrt

1048709 Ein Task-Zustand kann direkt von ldquorunningrdquo zu ldquodormantrdquo wechseln

1048709 Eine Task im Zustand ldquosuspendedrdquo kann direkt in den Zustand ldquorunningrdquo wechseln

1048709 Eine Task im Zustand ldquodormantrdquo ist nicht bereit da Zeit- oder andere Bedingungen nicht

erfuumlllt sind

1048709 Eine Task im Zustand ldquosuspendedrdquo wartet auf das Auftreten eines Events

Seite 14

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Zustandsuumlbergaumlnge (Umhaumlngen in eine andere Liste) bull Es existieren drei Arten des Prozessor-Entzugs

ndash Aufgabe des Prozessors durch einen Warteaufruf Wartelistendash Verdraumlngung durch einen anderen Prozess (Praumlemption) Bereitlistendash Beendigung

bull Vom Zustand bdquoblockiertldquo geht es nicht direkt in den Zustand bdquorunningldquobull Der Uumlbergang von bdquorunningldquo nach bdquoblockiertldquo wird immer durch den Prozess selbst

initiiertbull Der Uumlbergang von bdquorunningldquo nach bdquobeendetldquo wird immer durch den Prozess selbst

initiiertbull Der Uumlbergang von bdquobereitldquo nach bdquorunningldquo und zuruumlck geschieht immer durch das

Betriebssystem

Seite 15

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Leichtgewichtsprozesse (Threads)bull Threads sind parallele Kontrollfluumlsse die nicht gegeneinander abgeschottet sind

ndash laufen innerhalb des Adressraums eines bdquoechtenldquo Rechenprozessesndash teilen sich gemeinsame Ressourcen (zB globale Variable)

bull Es gibt Threads im Betriebssystem-Kernel Scheduling durch BSbull Es gibt Threads im Usermodus des Betriebssystems Scheduling durch Anwendung

BS nur fuumlr Prozess-Scheduling verantwortlich

Kernel

Usermodus

Prozess

Thread

Seite 16

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Unterschiede zwischen Tasks und Threads

bull Aus Sicht der Betriebszustaumlnde der Zeitparameter des Schedulings und der Synchronisation sind Thread und Task gleich

Task Thread

Besitzer von Betriebsmitteln Kann auszliger Prozessor selbst keine Betriebsmittel besitzen verfuumlgt aber uumlber alle Betriebsmittel der Task der er angehoumlrt

Eigener Adressraum Adressraum der Task der er angehoumlrt Threads haben einen gemeinsamen Adressraum

Enthaumllt einen oder mehrere Tasks Element einer Task

Kommunikation uumlber Taskgrenzen hinaus bevorzugt uumlber Botschaften

Kommunikation zwischen den Threads bevorzugt uumlber gleiche Daten

Task wird charakterisiert uumlber einen PCB

Thread wird charakterisiert uumlber Programmzaumlhler Register Stack und Zustand

Seite 17

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Vorteile von Threadsbull Kontextwechsel zwischen Threads effizienter als zwischen Prozessen

ndash kein Wechsel des Adressraumsndash kein automatisches Schedulingndash kein Retten und Restaurieren des Kontextes (nur Programmzaumlhler und Register)

bull Pro Zeiteinheit sind viel mehr Threadwechsel als Prozesswechsel moumlglich deshalb auch bdquoleichtgewichtigeldquo Prozesse

bull Einfachere Programmierung (gegenuumlber Tasks) wenn mehrere gleichzeitige Aktivitaumlten von denen einige von Zeit zu Zeit blockieren modelliert werden muumlssen

bull Bessere Performance bei Erzeugung und Zerstoumlrung da keine Ressourcen mit Threads verbunden sind

bull Bessere Performance bei Mischung von CPU- mit IO-intensiven Aufgaben (kein Vorteil bei reiner CPU-Nutzung

bull ABER Da die Schutzfunktion der getrennten Adressraumlume fehlt werden Synchronisationsmechanismen benoumltigt

Seite 18

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselbull Zur Erinnerung

ndash Auf einem Rechner laufen mehrere Prozessendash Es gibt meist nur eine CPUndash Das heiszligt die Prozesse muumlssen sich in der Nutzung der CPU abwechselnndash Das Betriebssystem entscheidet welcher Prozess als naumlchstes die CPU benutzen

darfbull Komponenten des Scheduling

ndash Prozesswechselkostenndash Warteschlangenmodellendash Scheduling-Verfahren

Seite 19

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselkostenbull Ein Prozesswechsel zwischen 2 Prozessen A und B schlieszligt genau genommen drei

weitere mit einndash Prozess A Unterbrechungsbearbeitung (UB)ndash UB Betriebssystem (BS)ndash BS Prozess Bndash Prozess B BS

ndash BS Prozess A

BS

Unterbr

Prozess A

Prozess B

1 KW (Kontextwechsel)

2 KW

3 KW 4 KW

5 KW

Prozess A ist verdraumlngt

bull Beim Prozesswechsel muss der Kontext des Prozesses im PCB gesichert werden dh beim 1 PW save state into PCBA und reload state from PCBB

bull Prozesswechsel sind relativ teuer (zB 122 μs auf Sun Sparc 20) 2 Prozesswechsel1 Prozesswechsel

(PW)

Seite 20

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodellebull Prozesse werden intern in Warteschlangen gehalten wenn ihnen die angeforderten

Betriebsmittel (zB die CPU) nicht zur Verfuumlgung stehen oder die erwarteten Ereignisse (zB Beendigung eines Prozesses) noch nicht eingetreten sind

bull Die Auswahlstrategien der Warteschlangen haben wesentlichen Einfluss auf das Systemverhalten

bull Prozesse migrieren aus Sicht des Betriebssystems zwischen den verschiedenen Warteschlangen

ndash Job queue (Prozessliste) Menge aller Prozesse im Systemndash Ready queue (Bereitliste CPU-Warteschlange) Menge der Prozesse die im

Hauptspeicher geladen und bereit zur Ausfuumlhrung sindndash Device queues (Warteschlange fuumlr jedes Geraumlt) Menge der Prozesse die auf ein

IO-Geraumlt warten

Seite 21

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Prozesse migrieren zwischen den Warteschlangen

Seite 22

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Beispiel

Seite 23

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Seite 24

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Ankunftszeit Task wird in Taskliste aufgenommen

Anforderungszeit Ereignis tritt ein Task wird ablaufwilligStartzeit Task erhaumllt

erstmalig die CPU zugeteilt

Beendigungszeit Task hat Aufgabe erledigt und ruht wieder

Deadline Zeit zu der die Task spaumltestens beendet sein muss

Ausfuumlhrungszeit Rechenzeit der Task (ohne Wartezeiten)

Periode Zeitdifferenz zwischen aufeinander folgenden Anforderungen

Spielraum Restzeit zwischen Beendigung und Deadline

Reaktionszeit Zeit zwischen Anfor-derung und Start der Ausfuumlhrung

Seite 25

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

ai Ankunftszeit (Arrival Time) Zeitpunkt an dem eine Task dem Betriebssystem bekannt gemacht wird die Taskverwaltung nimmt die Task in die Taskliste und setzt sie in den Zustand ruhend

ri Anforderungszeit (Request Time) Die Task bewirbt sich bei der Taskverwaltung um den Prozessor

si Startzeit (Start Time) die Task erhaumllt den Prozessor zugeteilt

ci Beendigungszeit (Completion Time) Die Task hat ihre Aufgabe erledigt und kehrt in den Zustand ruhend zuruumlck

di Zeitschranke (Deadline) Zeitpunkt an dem die Taskausfuumlhrung spaumltestens beendet sein muss Die Zeitschranke kann hart fest oder weich sein

pi Periode (Period) Zeitdauer kennzeichnet die Wiederholungsrate bei periodischen Tasks sie ergibt sich aus der Zeitdifferenz zwischen zwei aufeinander folgenden Anforderungszeiten einer Task

ei Ausfuumlhrungszeit (Execution Time) Zeitdauer die eine Task zur Ausfuumlhrung ihrer Aufgabe benoumltigt wenn sie sich im Zustand laufend befindet Eine Variante ist die maximale Ausfuumlhrungszeit (worst case execution time = WCET) eine obere Schranke der Ausfuumlhrungszeit die in keinem Fall uumlberschritten werden darf

li Spielraum (Laxity) verbleibende Restzeit zwischen Beendigungszeit und Zeitschranke

ji Reaktionszeit (Reaction Time Release Jitter) Zeitraum kennzeichnet die Verzoumlgerung zwischen Anforderung und dem Start der Ausfuumlhrung

Seite 26

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Uumlbungsfragen (Vorl Uni Stuttgart)

1048709 Eine Task im Zustand ldquorunnablerdquo wird momentan ausgefuumlhrt

1048709 Ein Task-Zustand kann direkt von ldquorunningrdquo zu ldquodormantrdquo wechseln

1048709 Eine Task im Zustand ldquosuspendedrdquo kann direkt in den Zustand ldquorunningrdquo wechseln

1048709 Eine Task im Zustand ldquodormantrdquo ist nicht bereit da Zeit- oder andere Bedingungen nicht

erfuumlllt sind

1048709 Eine Task im Zustand ldquosuspendedrdquo wartet auf das Auftreten eines Events

Seite 15

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Leichtgewichtsprozesse (Threads)bull Threads sind parallele Kontrollfluumlsse die nicht gegeneinander abgeschottet sind

ndash laufen innerhalb des Adressraums eines bdquoechtenldquo Rechenprozessesndash teilen sich gemeinsame Ressourcen (zB globale Variable)

bull Es gibt Threads im Betriebssystem-Kernel Scheduling durch BSbull Es gibt Threads im Usermodus des Betriebssystems Scheduling durch Anwendung

BS nur fuumlr Prozess-Scheduling verantwortlich

Kernel

Usermodus

Prozess

Thread

Seite 16

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Unterschiede zwischen Tasks und Threads

bull Aus Sicht der Betriebszustaumlnde der Zeitparameter des Schedulings und der Synchronisation sind Thread und Task gleich

Task Thread

Besitzer von Betriebsmitteln Kann auszliger Prozessor selbst keine Betriebsmittel besitzen verfuumlgt aber uumlber alle Betriebsmittel der Task der er angehoumlrt

Eigener Adressraum Adressraum der Task der er angehoumlrt Threads haben einen gemeinsamen Adressraum

Enthaumllt einen oder mehrere Tasks Element einer Task

Kommunikation uumlber Taskgrenzen hinaus bevorzugt uumlber Botschaften

Kommunikation zwischen den Threads bevorzugt uumlber gleiche Daten

Task wird charakterisiert uumlber einen PCB

Thread wird charakterisiert uumlber Programmzaumlhler Register Stack und Zustand

Seite 17

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Vorteile von Threadsbull Kontextwechsel zwischen Threads effizienter als zwischen Prozessen

ndash kein Wechsel des Adressraumsndash kein automatisches Schedulingndash kein Retten und Restaurieren des Kontextes (nur Programmzaumlhler und Register)

bull Pro Zeiteinheit sind viel mehr Threadwechsel als Prozesswechsel moumlglich deshalb auch bdquoleichtgewichtigeldquo Prozesse

bull Einfachere Programmierung (gegenuumlber Tasks) wenn mehrere gleichzeitige Aktivitaumlten von denen einige von Zeit zu Zeit blockieren modelliert werden muumlssen

bull Bessere Performance bei Erzeugung und Zerstoumlrung da keine Ressourcen mit Threads verbunden sind

bull Bessere Performance bei Mischung von CPU- mit IO-intensiven Aufgaben (kein Vorteil bei reiner CPU-Nutzung

bull ABER Da die Schutzfunktion der getrennten Adressraumlume fehlt werden Synchronisationsmechanismen benoumltigt

Seite 18

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselbull Zur Erinnerung

ndash Auf einem Rechner laufen mehrere Prozessendash Es gibt meist nur eine CPUndash Das heiszligt die Prozesse muumlssen sich in der Nutzung der CPU abwechselnndash Das Betriebssystem entscheidet welcher Prozess als naumlchstes die CPU benutzen

darfbull Komponenten des Scheduling

ndash Prozesswechselkostenndash Warteschlangenmodellendash Scheduling-Verfahren

Seite 19

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselkostenbull Ein Prozesswechsel zwischen 2 Prozessen A und B schlieszligt genau genommen drei

weitere mit einndash Prozess A Unterbrechungsbearbeitung (UB)ndash UB Betriebssystem (BS)ndash BS Prozess Bndash Prozess B BS

ndash BS Prozess A

BS

Unterbr

Prozess A

Prozess B

1 KW (Kontextwechsel)

2 KW

3 KW 4 KW

5 KW

Prozess A ist verdraumlngt

bull Beim Prozesswechsel muss der Kontext des Prozesses im PCB gesichert werden dh beim 1 PW save state into PCBA und reload state from PCBB

bull Prozesswechsel sind relativ teuer (zB 122 μs auf Sun Sparc 20) 2 Prozesswechsel1 Prozesswechsel

(PW)

Seite 20

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodellebull Prozesse werden intern in Warteschlangen gehalten wenn ihnen die angeforderten

Betriebsmittel (zB die CPU) nicht zur Verfuumlgung stehen oder die erwarteten Ereignisse (zB Beendigung eines Prozesses) noch nicht eingetreten sind

bull Die Auswahlstrategien der Warteschlangen haben wesentlichen Einfluss auf das Systemverhalten

bull Prozesse migrieren aus Sicht des Betriebssystems zwischen den verschiedenen Warteschlangen

ndash Job queue (Prozessliste) Menge aller Prozesse im Systemndash Ready queue (Bereitliste CPU-Warteschlange) Menge der Prozesse die im

Hauptspeicher geladen und bereit zur Ausfuumlhrung sindndash Device queues (Warteschlange fuumlr jedes Geraumlt) Menge der Prozesse die auf ein

IO-Geraumlt warten

Seite 21

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Prozesse migrieren zwischen den Warteschlangen

Seite 22

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Beispiel

Seite 23

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Seite 24

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Ankunftszeit Task wird in Taskliste aufgenommen

Anforderungszeit Ereignis tritt ein Task wird ablaufwilligStartzeit Task erhaumllt

erstmalig die CPU zugeteilt

Beendigungszeit Task hat Aufgabe erledigt und ruht wieder

Deadline Zeit zu der die Task spaumltestens beendet sein muss

Ausfuumlhrungszeit Rechenzeit der Task (ohne Wartezeiten)

Periode Zeitdifferenz zwischen aufeinander folgenden Anforderungen

Spielraum Restzeit zwischen Beendigung und Deadline

Reaktionszeit Zeit zwischen Anfor-derung und Start der Ausfuumlhrung

Seite 25

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

ai Ankunftszeit (Arrival Time) Zeitpunkt an dem eine Task dem Betriebssystem bekannt gemacht wird die Taskverwaltung nimmt die Task in die Taskliste und setzt sie in den Zustand ruhend

ri Anforderungszeit (Request Time) Die Task bewirbt sich bei der Taskverwaltung um den Prozessor

si Startzeit (Start Time) die Task erhaumllt den Prozessor zugeteilt

ci Beendigungszeit (Completion Time) Die Task hat ihre Aufgabe erledigt und kehrt in den Zustand ruhend zuruumlck

di Zeitschranke (Deadline) Zeitpunkt an dem die Taskausfuumlhrung spaumltestens beendet sein muss Die Zeitschranke kann hart fest oder weich sein

pi Periode (Period) Zeitdauer kennzeichnet die Wiederholungsrate bei periodischen Tasks sie ergibt sich aus der Zeitdifferenz zwischen zwei aufeinander folgenden Anforderungszeiten einer Task

ei Ausfuumlhrungszeit (Execution Time) Zeitdauer die eine Task zur Ausfuumlhrung ihrer Aufgabe benoumltigt wenn sie sich im Zustand laufend befindet Eine Variante ist die maximale Ausfuumlhrungszeit (worst case execution time = WCET) eine obere Schranke der Ausfuumlhrungszeit die in keinem Fall uumlberschritten werden darf

li Spielraum (Laxity) verbleibende Restzeit zwischen Beendigungszeit und Zeitschranke

ji Reaktionszeit (Reaction Time Release Jitter) Zeitraum kennzeichnet die Verzoumlgerung zwischen Anforderung und dem Start der Ausfuumlhrung

Seite 26

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Uumlbungsfragen (Vorl Uni Stuttgart)

1048709 Eine Task im Zustand ldquorunnablerdquo wird momentan ausgefuumlhrt

1048709 Ein Task-Zustand kann direkt von ldquorunningrdquo zu ldquodormantrdquo wechseln

1048709 Eine Task im Zustand ldquosuspendedrdquo kann direkt in den Zustand ldquorunningrdquo wechseln

1048709 Eine Task im Zustand ldquodormantrdquo ist nicht bereit da Zeit- oder andere Bedingungen nicht

erfuumlllt sind

1048709 Eine Task im Zustand ldquosuspendedrdquo wartet auf das Auftreten eines Events

Seite 16

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Unterschiede zwischen Tasks und Threads

bull Aus Sicht der Betriebszustaumlnde der Zeitparameter des Schedulings und der Synchronisation sind Thread und Task gleich

Task Thread

Besitzer von Betriebsmitteln Kann auszliger Prozessor selbst keine Betriebsmittel besitzen verfuumlgt aber uumlber alle Betriebsmittel der Task der er angehoumlrt

Eigener Adressraum Adressraum der Task der er angehoumlrt Threads haben einen gemeinsamen Adressraum

Enthaumllt einen oder mehrere Tasks Element einer Task

Kommunikation uumlber Taskgrenzen hinaus bevorzugt uumlber Botschaften

Kommunikation zwischen den Threads bevorzugt uumlber gleiche Daten

Task wird charakterisiert uumlber einen PCB

Thread wird charakterisiert uumlber Programmzaumlhler Register Stack und Zustand

Seite 17

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Vorteile von Threadsbull Kontextwechsel zwischen Threads effizienter als zwischen Prozessen

ndash kein Wechsel des Adressraumsndash kein automatisches Schedulingndash kein Retten und Restaurieren des Kontextes (nur Programmzaumlhler und Register)

bull Pro Zeiteinheit sind viel mehr Threadwechsel als Prozesswechsel moumlglich deshalb auch bdquoleichtgewichtigeldquo Prozesse

bull Einfachere Programmierung (gegenuumlber Tasks) wenn mehrere gleichzeitige Aktivitaumlten von denen einige von Zeit zu Zeit blockieren modelliert werden muumlssen

bull Bessere Performance bei Erzeugung und Zerstoumlrung da keine Ressourcen mit Threads verbunden sind

bull Bessere Performance bei Mischung von CPU- mit IO-intensiven Aufgaben (kein Vorteil bei reiner CPU-Nutzung

bull ABER Da die Schutzfunktion der getrennten Adressraumlume fehlt werden Synchronisationsmechanismen benoumltigt

Seite 18

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselbull Zur Erinnerung

ndash Auf einem Rechner laufen mehrere Prozessendash Es gibt meist nur eine CPUndash Das heiszligt die Prozesse muumlssen sich in der Nutzung der CPU abwechselnndash Das Betriebssystem entscheidet welcher Prozess als naumlchstes die CPU benutzen

darfbull Komponenten des Scheduling

ndash Prozesswechselkostenndash Warteschlangenmodellendash Scheduling-Verfahren

Seite 19

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselkostenbull Ein Prozesswechsel zwischen 2 Prozessen A und B schlieszligt genau genommen drei

weitere mit einndash Prozess A Unterbrechungsbearbeitung (UB)ndash UB Betriebssystem (BS)ndash BS Prozess Bndash Prozess B BS

ndash BS Prozess A

BS

Unterbr

Prozess A

Prozess B

1 KW (Kontextwechsel)

2 KW

3 KW 4 KW

5 KW

Prozess A ist verdraumlngt

bull Beim Prozesswechsel muss der Kontext des Prozesses im PCB gesichert werden dh beim 1 PW save state into PCBA und reload state from PCBB

bull Prozesswechsel sind relativ teuer (zB 122 μs auf Sun Sparc 20) 2 Prozesswechsel1 Prozesswechsel

(PW)

Seite 20

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodellebull Prozesse werden intern in Warteschlangen gehalten wenn ihnen die angeforderten

Betriebsmittel (zB die CPU) nicht zur Verfuumlgung stehen oder die erwarteten Ereignisse (zB Beendigung eines Prozesses) noch nicht eingetreten sind

bull Die Auswahlstrategien der Warteschlangen haben wesentlichen Einfluss auf das Systemverhalten

bull Prozesse migrieren aus Sicht des Betriebssystems zwischen den verschiedenen Warteschlangen

ndash Job queue (Prozessliste) Menge aller Prozesse im Systemndash Ready queue (Bereitliste CPU-Warteschlange) Menge der Prozesse die im

Hauptspeicher geladen und bereit zur Ausfuumlhrung sindndash Device queues (Warteschlange fuumlr jedes Geraumlt) Menge der Prozesse die auf ein

IO-Geraumlt warten

Seite 21

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Prozesse migrieren zwischen den Warteschlangen

Seite 22

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Beispiel

Seite 23

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Seite 24

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Ankunftszeit Task wird in Taskliste aufgenommen

Anforderungszeit Ereignis tritt ein Task wird ablaufwilligStartzeit Task erhaumllt

erstmalig die CPU zugeteilt

Beendigungszeit Task hat Aufgabe erledigt und ruht wieder

Deadline Zeit zu der die Task spaumltestens beendet sein muss

Ausfuumlhrungszeit Rechenzeit der Task (ohne Wartezeiten)

Periode Zeitdifferenz zwischen aufeinander folgenden Anforderungen

Spielraum Restzeit zwischen Beendigung und Deadline

Reaktionszeit Zeit zwischen Anfor-derung und Start der Ausfuumlhrung

Seite 25

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

ai Ankunftszeit (Arrival Time) Zeitpunkt an dem eine Task dem Betriebssystem bekannt gemacht wird die Taskverwaltung nimmt die Task in die Taskliste und setzt sie in den Zustand ruhend

ri Anforderungszeit (Request Time) Die Task bewirbt sich bei der Taskverwaltung um den Prozessor

si Startzeit (Start Time) die Task erhaumllt den Prozessor zugeteilt

ci Beendigungszeit (Completion Time) Die Task hat ihre Aufgabe erledigt und kehrt in den Zustand ruhend zuruumlck

di Zeitschranke (Deadline) Zeitpunkt an dem die Taskausfuumlhrung spaumltestens beendet sein muss Die Zeitschranke kann hart fest oder weich sein

pi Periode (Period) Zeitdauer kennzeichnet die Wiederholungsrate bei periodischen Tasks sie ergibt sich aus der Zeitdifferenz zwischen zwei aufeinander folgenden Anforderungszeiten einer Task

ei Ausfuumlhrungszeit (Execution Time) Zeitdauer die eine Task zur Ausfuumlhrung ihrer Aufgabe benoumltigt wenn sie sich im Zustand laufend befindet Eine Variante ist die maximale Ausfuumlhrungszeit (worst case execution time = WCET) eine obere Schranke der Ausfuumlhrungszeit die in keinem Fall uumlberschritten werden darf

li Spielraum (Laxity) verbleibende Restzeit zwischen Beendigungszeit und Zeitschranke

ji Reaktionszeit (Reaction Time Release Jitter) Zeitraum kennzeichnet die Verzoumlgerung zwischen Anforderung und dem Start der Ausfuumlhrung

Seite 26

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Uumlbungsfragen (Vorl Uni Stuttgart)

1048709 Eine Task im Zustand ldquorunnablerdquo wird momentan ausgefuumlhrt

1048709 Ein Task-Zustand kann direkt von ldquorunningrdquo zu ldquodormantrdquo wechseln

1048709 Eine Task im Zustand ldquosuspendedrdquo kann direkt in den Zustand ldquorunningrdquo wechseln

1048709 Eine Task im Zustand ldquodormantrdquo ist nicht bereit da Zeit- oder andere Bedingungen nicht

erfuumlllt sind

1048709 Eine Task im Zustand ldquosuspendedrdquo wartet auf das Auftreten eines Events

Seite 17

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Vorteile von Threadsbull Kontextwechsel zwischen Threads effizienter als zwischen Prozessen

ndash kein Wechsel des Adressraumsndash kein automatisches Schedulingndash kein Retten und Restaurieren des Kontextes (nur Programmzaumlhler und Register)

bull Pro Zeiteinheit sind viel mehr Threadwechsel als Prozesswechsel moumlglich deshalb auch bdquoleichtgewichtigeldquo Prozesse

bull Einfachere Programmierung (gegenuumlber Tasks) wenn mehrere gleichzeitige Aktivitaumlten von denen einige von Zeit zu Zeit blockieren modelliert werden muumlssen

bull Bessere Performance bei Erzeugung und Zerstoumlrung da keine Ressourcen mit Threads verbunden sind

bull Bessere Performance bei Mischung von CPU- mit IO-intensiven Aufgaben (kein Vorteil bei reiner CPU-Nutzung

bull ABER Da die Schutzfunktion der getrennten Adressraumlume fehlt werden Synchronisationsmechanismen benoumltigt

Seite 18

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselbull Zur Erinnerung

ndash Auf einem Rechner laufen mehrere Prozessendash Es gibt meist nur eine CPUndash Das heiszligt die Prozesse muumlssen sich in der Nutzung der CPU abwechselnndash Das Betriebssystem entscheidet welcher Prozess als naumlchstes die CPU benutzen

darfbull Komponenten des Scheduling

ndash Prozesswechselkostenndash Warteschlangenmodellendash Scheduling-Verfahren

Seite 19

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselkostenbull Ein Prozesswechsel zwischen 2 Prozessen A und B schlieszligt genau genommen drei

weitere mit einndash Prozess A Unterbrechungsbearbeitung (UB)ndash UB Betriebssystem (BS)ndash BS Prozess Bndash Prozess B BS

ndash BS Prozess A

BS

Unterbr

Prozess A

Prozess B

1 KW (Kontextwechsel)

2 KW

3 KW 4 KW

5 KW

Prozess A ist verdraumlngt

bull Beim Prozesswechsel muss der Kontext des Prozesses im PCB gesichert werden dh beim 1 PW save state into PCBA und reload state from PCBB

bull Prozesswechsel sind relativ teuer (zB 122 μs auf Sun Sparc 20) 2 Prozesswechsel1 Prozesswechsel

(PW)

Seite 20

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodellebull Prozesse werden intern in Warteschlangen gehalten wenn ihnen die angeforderten

Betriebsmittel (zB die CPU) nicht zur Verfuumlgung stehen oder die erwarteten Ereignisse (zB Beendigung eines Prozesses) noch nicht eingetreten sind

bull Die Auswahlstrategien der Warteschlangen haben wesentlichen Einfluss auf das Systemverhalten

bull Prozesse migrieren aus Sicht des Betriebssystems zwischen den verschiedenen Warteschlangen

ndash Job queue (Prozessliste) Menge aller Prozesse im Systemndash Ready queue (Bereitliste CPU-Warteschlange) Menge der Prozesse die im

Hauptspeicher geladen und bereit zur Ausfuumlhrung sindndash Device queues (Warteschlange fuumlr jedes Geraumlt) Menge der Prozesse die auf ein

IO-Geraumlt warten

Seite 21

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Prozesse migrieren zwischen den Warteschlangen

Seite 22

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Beispiel

Seite 23

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Seite 24

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Ankunftszeit Task wird in Taskliste aufgenommen

Anforderungszeit Ereignis tritt ein Task wird ablaufwilligStartzeit Task erhaumllt

erstmalig die CPU zugeteilt

Beendigungszeit Task hat Aufgabe erledigt und ruht wieder

Deadline Zeit zu der die Task spaumltestens beendet sein muss

Ausfuumlhrungszeit Rechenzeit der Task (ohne Wartezeiten)

Periode Zeitdifferenz zwischen aufeinander folgenden Anforderungen

Spielraum Restzeit zwischen Beendigung und Deadline

Reaktionszeit Zeit zwischen Anfor-derung und Start der Ausfuumlhrung

Seite 25

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

ai Ankunftszeit (Arrival Time) Zeitpunkt an dem eine Task dem Betriebssystem bekannt gemacht wird die Taskverwaltung nimmt die Task in die Taskliste und setzt sie in den Zustand ruhend

ri Anforderungszeit (Request Time) Die Task bewirbt sich bei der Taskverwaltung um den Prozessor

si Startzeit (Start Time) die Task erhaumllt den Prozessor zugeteilt

ci Beendigungszeit (Completion Time) Die Task hat ihre Aufgabe erledigt und kehrt in den Zustand ruhend zuruumlck

di Zeitschranke (Deadline) Zeitpunkt an dem die Taskausfuumlhrung spaumltestens beendet sein muss Die Zeitschranke kann hart fest oder weich sein

pi Periode (Period) Zeitdauer kennzeichnet die Wiederholungsrate bei periodischen Tasks sie ergibt sich aus der Zeitdifferenz zwischen zwei aufeinander folgenden Anforderungszeiten einer Task

ei Ausfuumlhrungszeit (Execution Time) Zeitdauer die eine Task zur Ausfuumlhrung ihrer Aufgabe benoumltigt wenn sie sich im Zustand laufend befindet Eine Variante ist die maximale Ausfuumlhrungszeit (worst case execution time = WCET) eine obere Schranke der Ausfuumlhrungszeit die in keinem Fall uumlberschritten werden darf

li Spielraum (Laxity) verbleibende Restzeit zwischen Beendigungszeit und Zeitschranke

ji Reaktionszeit (Reaction Time Release Jitter) Zeitraum kennzeichnet die Verzoumlgerung zwischen Anforderung und dem Start der Ausfuumlhrung

Seite 26

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Uumlbungsfragen (Vorl Uni Stuttgart)

1048709 Eine Task im Zustand ldquorunnablerdquo wird momentan ausgefuumlhrt

1048709 Ein Task-Zustand kann direkt von ldquorunningrdquo zu ldquodormantrdquo wechseln

1048709 Eine Task im Zustand ldquosuspendedrdquo kann direkt in den Zustand ldquorunningrdquo wechseln

1048709 Eine Task im Zustand ldquodormantrdquo ist nicht bereit da Zeit- oder andere Bedingungen nicht

erfuumlllt sind

1048709 Eine Task im Zustand ldquosuspendedrdquo wartet auf das Auftreten eines Events

Seite 18

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselbull Zur Erinnerung

ndash Auf einem Rechner laufen mehrere Prozessendash Es gibt meist nur eine CPUndash Das heiszligt die Prozesse muumlssen sich in der Nutzung der CPU abwechselnndash Das Betriebssystem entscheidet welcher Prozess als naumlchstes die CPU benutzen

darfbull Komponenten des Scheduling

ndash Prozesswechselkostenndash Warteschlangenmodellendash Scheduling-Verfahren

Seite 19

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselkostenbull Ein Prozesswechsel zwischen 2 Prozessen A und B schlieszligt genau genommen drei

weitere mit einndash Prozess A Unterbrechungsbearbeitung (UB)ndash UB Betriebssystem (BS)ndash BS Prozess Bndash Prozess B BS

ndash BS Prozess A

BS

Unterbr

Prozess A

Prozess B

1 KW (Kontextwechsel)

2 KW

3 KW 4 KW

5 KW

Prozess A ist verdraumlngt

bull Beim Prozesswechsel muss der Kontext des Prozesses im PCB gesichert werden dh beim 1 PW save state into PCBA und reload state from PCBB

bull Prozesswechsel sind relativ teuer (zB 122 μs auf Sun Sparc 20) 2 Prozesswechsel1 Prozesswechsel

(PW)

Seite 20

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodellebull Prozesse werden intern in Warteschlangen gehalten wenn ihnen die angeforderten

Betriebsmittel (zB die CPU) nicht zur Verfuumlgung stehen oder die erwarteten Ereignisse (zB Beendigung eines Prozesses) noch nicht eingetreten sind

bull Die Auswahlstrategien der Warteschlangen haben wesentlichen Einfluss auf das Systemverhalten

bull Prozesse migrieren aus Sicht des Betriebssystems zwischen den verschiedenen Warteschlangen

ndash Job queue (Prozessliste) Menge aller Prozesse im Systemndash Ready queue (Bereitliste CPU-Warteschlange) Menge der Prozesse die im

Hauptspeicher geladen und bereit zur Ausfuumlhrung sindndash Device queues (Warteschlange fuumlr jedes Geraumlt) Menge der Prozesse die auf ein

IO-Geraumlt warten

Seite 21

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Prozesse migrieren zwischen den Warteschlangen

Seite 22

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Beispiel

Seite 23

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Seite 24

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Ankunftszeit Task wird in Taskliste aufgenommen

Anforderungszeit Ereignis tritt ein Task wird ablaufwilligStartzeit Task erhaumllt

erstmalig die CPU zugeteilt

Beendigungszeit Task hat Aufgabe erledigt und ruht wieder

Deadline Zeit zu der die Task spaumltestens beendet sein muss

Ausfuumlhrungszeit Rechenzeit der Task (ohne Wartezeiten)

Periode Zeitdifferenz zwischen aufeinander folgenden Anforderungen

Spielraum Restzeit zwischen Beendigung und Deadline

Reaktionszeit Zeit zwischen Anfor-derung und Start der Ausfuumlhrung

Seite 25

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

ai Ankunftszeit (Arrival Time) Zeitpunkt an dem eine Task dem Betriebssystem bekannt gemacht wird die Taskverwaltung nimmt die Task in die Taskliste und setzt sie in den Zustand ruhend

ri Anforderungszeit (Request Time) Die Task bewirbt sich bei der Taskverwaltung um den Prozessor

si Startzeit (Start Time) die Task erhaumllt den Prozessor zugeteilt

ci Beendigungszeit (Completion Time) Die Task hat ihre Aufgabe erledigt und kehrt in den Zustand ruhend zuruumlck

di Zeitschranke (Deadline) Zeitpunkt an dem die Taskausfuumlhrung spaumltestens beendet sein muss Die Zeitschranke kann hart fest oder weich sein

pi Periode (Period) Zeitdauer kennzeichnet die Wiederholungsrate bei periodischen Tasks sie ergibt sich aus der Zeitdifferenz zwischen zwei aufeinander folgenden Anforderungszeiten einer Task

ei Ausfuumlhrungszeit (Execution Time) Zeitdauer die eine Task zur Ausfuumlhrung ihrer Aufgabe benoumltigt wenn sie sich im Zustand laufend befindet Eine Variante ist die maximale Ausfuumlhrungszeit (worst case execution time = WCET) eine obere Schranke der Ausfuumlhrungszeit die in keinem Fall uumlberschritten werden darf

li Spielraum (Laxity) verbleibende Restzeit zwischen Beendigungszeit und Zeitschranke

ji Reaktionszeit (Reaction Time Release Jitter) Zeitraum kennzeichnet die Verzoumlgerung zwischen Anforderung und dem Start der Ausfuumlhrung

Seite 26

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Uumlbungsfragen (Vorl Uni Stuttgart)

1048709 Eine Task im Zustand ldquorunnablerdquo wird momentan ausgefuumlhrt

1048709 Ein Task-Zustand kann direkt von ldquorunningrdquo zu ldquodormantrdquo wechseln

1048709 Eine Task im Zustand ldquosuspendedrdquo kann direkt in den Zustand ldquorunningrdquo wechseln

1048709 Eine Task im Zustand ldquodormantrdquo ist nicht bereit da Zeit- oder andere Bedingungen nicht

erfuumlllt sind

1048709 Eine Task im Zustand ldquosuspendedrdquo wartet auf das Auftreten eines Events

Seite 19

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Prozesswechselkostenbull Ein Prozesswechsel zwischen 2 Prozessen A und B schlieszligt genau genommen drei

weitere mit einndash Prozess A Unterbrechungsbearbeitung (UB)ndash UB Betriebssystem (BS)ndash BS Prozess Bndash Prozess B BS

ndash BS Prozess A

BS

Unterbr

Prozess A

Prozess B

1 KW (Kontextwechsel)

2 KW

3 KW 4 KW

5 KW

Prozess A ist verdraumlngt

bull Beim Prozesswechsel muss der Kontext des Prozesses im PCB gesichert werden dh beim 1 PW save state into PCBA und reload state from PCBB

bull Prozesswechsel sind relativ teuer (zB 122 μs auf Sun Sparc 20) 2 Prozesswechsel1 Prozesswechsel

(PW)

Seite 20

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodellebull Prozesse werden intern in Warteschlangen gehalten wenn ihnen die angeforderten

Betriebsmittel (zB die CPU) nicht zur Verfuumlgung stehen oder die erwarteten Ereignisse (zB Beendigung eines Prozesses) noch nicht eingetreten sind

bull Die Auswahlstrategien der Warteschlangen haben wesentlichen Einfluss auf das Systemverhalten

bull Prozesse migrieren aus Sicht des Betriebssystems zwischen den verschiedenen Warteschlangen

ndash Job queue (Prozessliste) Menge aller Prozesse im Systemndash Ready queue (Bereitliste CPU-Warteschlange) Menge der Prozesse die im

Hauptspeicher geladen und bereit zur Ausfuumlhrung sindndash Device queues (Warteschlange fuumlr jedes Geraumlt) Menge der Prozesse die auf ein

IO-Geraumlt warten

Seite 21

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Prozesse migrieren zwischen den Warteschlangen

Seite 22

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Beispiel

Seite 23

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Seite 24

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Ankunftszeit Task wird in Taskliste aufgenommen

Anforderungszeit Ereignis tritt ein Task wird ablaufwilligStartzeit Task erhaumllt

erstmalig die CPU zugeteilt

Beendigungszeit Task hat Aufgabe erledigt und ruht wieder

Deadline Zeit zu der die Task spaumltestens beendet sein muss

Ausfuumlhrungszeit Rechenzeit der Task (ohne Wartezeiten)

Periode Zeitdifferenz zwischen aufeinander folgenden Anforderungen

Spielraum Restzeit zwischen Beendigung und Deadline

Reaktionszeit Zeit zwischen Anfor-derung und Start der Ausfuumlhrung

Seite 25

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

ai Ankunftszeit (Arrival Time) Zeitpunkt an dem eine Task dem Betriebssystem bekannt gemacht wird die Taskverwaltung nimmt die Task in die Taskliste und setzt sie in den Zustand ruhend

ri Anforderungszeit (Request Time) Die Task bewirbt sich bei der Taskverwaltung um den Prozessor

si Startzeit (Start Time) die Task erhaumllt den Prozessor zugeteilt

ci Beendigungszeit (Completion Time) Die Task hat ihre Aufgabe erledigt und kehrt in den Zustand ruhend zuruumlck

di Zeitschranke (Deadline) Zeitpunkt an dem die Taskausfuumlhrung spaumltestens beendet sein muss Die Zeitschranke kann hart fest oder weich sein

pi Periode (Period) Zeitdauer kennzeichnet die Wiederholungsrate bei periodischen Tasks sie ergibt sich aus der Zeitdifferenz zwischen zwei aufeinander folgenden Anforderungszeiten einer Task

ei Ausfuumlhrungszeit (Execution Time) Zeitdauer die eine Task zur Ausfuumlhrung ihrer Aufgabe benoumltigt wenn sie sich im Zustand laufend befindet Eine Variante ist die maximale Ausfuumlhrungszeit (worst case execution time = WCET) eine obere Schranke der Ausfuumlhrungszeit die in keinem Fall uumlberschritten werden darf

li Spielraum (Laxity) verbleibende Restzeit zwischen Beendigungszeit und Zeitschranke

ji Reaktionszeit (Reaction Time Release Jitter) Zeitraum kennzeichnet die Verzoumlgerung zwischen Anforderung und dem Start der Ausfuumlhrung

Seite 26

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Uumlbungsfragen (Vorl Uni Stuttgart)

1048709 Eine Task im Zustand ldquorunnablerdquo wird momentan ausgefuumlhrt

1048709 Ein Task-Zustand kann direkt von ldquorunningrdquo zu ldquodormantrdquo wechseln

1048709 Eine Task im Zustand ldquosuspendedrdquo kann direkt in den Zustand ldquorunningrdquo wechseln

1048709 Eine Task im Zustand ldquodormantrdquo ist nicht bereit da Zeit- oder andere Bedingungen nicht

erfuumlllt sind

1048709 Eine Task im Zustand ldquosuspendedrdquo wartet auf das Auftreten eines Events

Seite 20

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodellebull Prozesse werden intern in Warteschlangen gehalten wenn ihnen die angeforderten

Betriebsmittel (zB die CPU) nicht zur Verfuumlgung stehen oder die erwarteten Ereignisse (zB Beendigung eines Prozesses) noch nicht eingetreten sind

bull Die Auswahlstrategien der Warteschlangen haben wesentlichen Einfluss auf das Systemverhalten

bull Prozesse migrieren aus Sicht des Betriebssystems zwischen den verschiedenen Warteschlangen

ndash Job queue (Prozessliste) Menge aller Prozesse im Systemndash Ready queue (Bereitliste CPU-Warteschlange) Menge der Prozesse die im

Hauptspeicher geladen und bereit zur Ausfuumlhrung sindndash Device queues (Warteschlange fuumlr jedes Geraumlt) Menge der Prozesse die auf ein

IO-Geraumlt warten

Seite 21

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Prozesse migrieren zwischen den Warteschlangen

Seite 22

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Beispiel

Seite 23

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Seite 24

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Ankunftszeit Task wird in Taskliste aufgenommen

Anforderungszeit Ereignis tritt ein Task wird ablaufwilligStartzeit Task erhaumllt

erstmalig die CPU zugeteilt

Beendigungszeit Task hat Aufgabe erledigt und ruht wieder

Deadline Zeit zu der die Task spaumltestens beendet sein muss

Ausfuumlhrungszeit Rechenzeit der Task (ohne Wartezeiten)

Periode Zeitdifferenz zwischen aufeinander folgenden Anforderungen

Spielraum Restzeit zwischen Beendigung und Deadline

Reaktionszeit Zeit zwischen Anfor-derung und Start der Ausfuumlhrung

Seite 25

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

ai Ankunftszeit (Arrival Time) Zeitpunkt an dem eine Task dem Betriebssystem bekannt gemacht wird die Taskverwaltung nimmt die Task in die Taskliste und setzt sie in den Zustand ruhend

ri Anforderungszeit (Request Time) Die Task bewirbt sich bei der Taskverwaltung um den Prozessor

si Startzeit (Start Time) die Task erhaumllt den Prozessor zugeteilt

ci Beendigungszeit (Completion Time) Die Task hat ihre Aufgabe erledigt und kehrt in den Zustand ruhend zuruumlck

di Zeitschranke (Deadline) Zeitpunkt an dem die Taskausfuumlhrung spaumltestens beendet sein muss Die Zeitschranke kann hart fest oder weich sein

pi Periode (Period) Zeitdauer kennzeichnet die Wiederholungsrate bei periodischen Tasks sie ergibt sich aus der Zeitdifferenz zwischen zwei aufeinander folgenden Anforderungszeiten einer Task

ei Ausfuumlhrungszeit (Execution Time) Zeitdauer die eine Task zur Ausfuumlhrung ihrer Aufgabe benoumltigt wenn sie sich im Zustand laufend befindet Eine Variante ist die maximale Ausfuumlhrungszeit (worst case execution time = WCET) eine obere Schranke der Ausfuumlhrungszeit die in keinem Fall uumlberschritten werden darf

li Spielraum (Laxity) verbleibende Restzeit zwischen Beendigungszeit und Zeitschranke

ji Reaktionszeit (Reaction Time Release Jitter) Zeitraum kennzeichnet die Verzoumlgerung zwischen Anforderung und dem Start der Ausfuumlhrung

Seite 26

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Uumlbungsfragen (Vorl Uni Stuttgart)

1048709 Eine Task im Zustand ldquorunnablerdquo wird momentan ausgefuumlhrt

1048709 Ein Task-Zustand kann direkt von ldquorunningrdquo zu ldquodormantrdquo wechseln

1048709 Eine Task im Zustand ldquosuspendedrdquo kann direkt in den Zustand ldquorunningrdquo wechseln

1048709 Eine Task im Zustand ldquodormantrdquo ist nicht bereit da Zeit- oder andere Bedingungen nicht

erfuumlllt sind

1048709 Eine Task im Zustand ldquosuspendedrdquo wartet auf das Auftreten eines Events

Seite 21

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Prozesse migrieren zwischen den Warteschlangen

Seite 22

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Beispiel

Seite 23

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Seite 24

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Ankunftszeit Task wird in Taskliste aufgenommen

Anforderungszeit Ereignis tritt ein Task wird ablaufwilligStartzeit Task erhaumllt

erstmalig die CPU zugeteilt

Beendigungszeit Task hat Aufgabe erledigt und ruht wieder

Deadline Zeit zu der die Task spaumltestens beendet sein muss

Ausfuumlhrungszeit Rechenzeit der Task (ohne Wartezeiten)

Periode Zeitdifferenz zwischen aufeinander folgenden Anforderungen

Spielraum Restzeit zwischen Beendigung und Deadline

Reaktionszeit Zeit zwischen Anfor-derung und Start der Ausfuumlhrung

Seite 25

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

ai Ankunftszeit (Arrival Time) Zeitpunkt an dem eine Task dem Betriebssystem bekannt gemacht wird die Taskverwaltung nimmt die Task in die Taskliste und setzt sie in den Zustand ruhend

ri Anforderungszeit (Request Time) Die Task bewirbt sich bei der Taskverwaltung um den Prozessor

si Startzeit (Start Time) die Task erhaumllt den Prozessor zugeteilt

ci Beendigungszeit (Completion Time) Die Task hat ihre Aufgabe erledigt und kehrt in den Zustand ruhend zuruumlck

di Zeitschranke (Deadline) Zeitpunkt an dem die Taskausfuumlhrung spaumltestens beendet sein muss Die Zeitschranke kann hart fest oder weich sein

pi Periode (Period) Zeitdauer kennzeichnet die Wiederholungsrate bei periodischen Tasks sie ergibt sich aus der Zeitdifferenz zwischen zwei aufeinander folgenden Anforderungszeiten einer Task

ei Ausfuumlhrungszeit (Execution Time) Zeitdauer die eine Task zur Ausfuumlhrung ihrer Aufgabe benoumltigt wenn sie sich im Zustand laufend befindet Eine Variante ist die maximale Ausfuumlhrungszeit (worst case execution time = WCET) eine obere Schranke der Ausfuumlhrungszeit die in keinem Fall uumlberschritten werden darf

li Spielraum (Laxity) verbleibende Restzeit zwischen Beendigungszeit und Zeitschranke

ji Reaktionszeit (Reaction Time Release Jitter) Zeitraum kennzeichnet die Verzoumlgerung zwischen Anforderung und dem Start der Ausfuumlhrung

Seite 26

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Uumlbungsfragen (Vorl Uni Stuttgart)

1048709 Eine Task im Zustand ldquorunnablerdquo wird momentan ausgefuumlhrt

1048709 Ein Task-Zustand kann direkt von ldquorunningrdquo zu ldquodormantrdquo wechseln

1048709 Eine Task im Zustand ldquosuspendedrdquo kann direkt in den Zustand ldquorunningrdquo wechseln

1048709 Eine Task im Zustand ldquodormantrdquo ist nicht bereit da Zeit- oder andere Bedingungen nicht

erfuumlllt sind

1048709 Eine Task im Zustand ldquosuspendedrdquo wartet auf das Auftreten eines Events

Seite 22

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Warteschlangenmodelle

Beispiel

Seite 23

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Seite 24

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Ankunftszeit Task wird in Taskliste aufgenommen

Anforderungszeit Ereignis tritt ein Task wird ablaufwilligStartzeit Task erhaumllt

erstmalig die CPU zugeteilt

Beendigungszeit Task hat Aufgabe erledigt und ruht wieder

Deadline Zeit zu der die Task spaumltestens beendet sein muss

Ausfuumlhrungszeit Rechenzeit der Task (ohne Wartezeiten)

Periode Zeitdifferenz zwischen aufeinander folgenden Anforderungen

Spielraum Restzeit zwischen Beendigung und Deadline

Reaktionszeit Zeit zwischen Anfor-derung und Start der Ausfuumlhrung

Seite 25

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

ai Ankunftszeit (Arrival Time) Zeitpunkt an dem eine Task dem Betriebssystem bekannt gemacht wird die Taskverwaltung nimmt die Task in die Taskliste und setzt sie in den Zustand ruhend

ri Anforderungszeit (Request Time) Die Task bewirbt sich bei der Taskverwaltung um den Prozessor

si Startzeit (Start Time) die Task erhaumllt den Prozessor zugeteilt

ci Beendigungszeit (Completion Time) Die Task hat ihre Aufgabe erledigt und kehrt in den Zustand ruhend zuruumlck

di Zeitschranke (Deadline) Zeitpunkt an dem die Taskausfuumlhrung spaumltestens beendet sein muss Die Zeitschranke kann hart fest oder weich sein

pi Periode (Period) Zeitdauer kennzeichnet die Wiederholungsrate bei periodischen Tasks sie ergibt sich aus der Zeitdifferenz zwischen zwei aufeinander folgenden Anforderungszeiten einer Task

ei Ausfuumlhrungszeit (Execution Time) Zeitdauer die eine Task zur Ausfuumlhrung ihrer Aufgabe benoumltigt wenn sie sich im Zustand laufend befindet Eine Variante ist die maximale Ausfuumlhrungszeit (worst case execution time = WCET) eine obere Schranke der Ausfuumlhrungszeit die in keinem Fall uumlberschritten werden darf

li Spielraum (Laxity) verbleibende Restzeit zwischen Beendigungszeit und Zeitschranke

ji Reaktionszeit (Reaction Time Release Jitter) Zeitraum kennzeichnet die Verzoumlgerung zwischen Anforderung und dem Start der Ausfuumlhrung

Seite 26

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Uumlbungsfragen (Vorl Uni Stuttgart)

1048709 Eine Task im Zustand ldquorunnablerdquo wird momentan ausgefuumlhrt

1048709 Ein Task-Zustand kann direkt von ldquorunningrdquo zu ldquodormantrdquo wechseln

1048709 Eine Task im Zustand ldquosuspendedrdquo kann direkt in den Zustand ldquorunningrdquo wechseln

1048709 Eine Task im Zustand ldquodormantrdquo ist nicht bereit da Zeit- oder andere Bedingungen nicht

erfuumlllt sind

1048709 Eine Task im Zustand ldquosuspendedrdquo wartet auf das Auftreten eines Events

Seite 23

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Seite 24

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Ankunftszeit Task wird in Taskliste aufgenommen

Anforderungszeit Ereignis tritt ein Task wird ablaufwilligStartzeit Task erhaumllt

erstmalig die CPU zugeteilt

Beendigungszeit Task hat Aufgabe erledigt und ruht wieder

Deadline Zeit zu der die Task spaumltestens beendet sein muss

Ausfuumlhrungszeit Rechenzeit der Task (ohne Wartezeiten)

Periode Zeitdifferenz zwischen aufeinander folgenden Anforderungen

Spielraum Restzeit zwischen Beendigung und Deadline

Reaktionszeit Zeit zwischen Anfor-derung und Start der Ausfuumlhrung

Seite 25

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

ai Ankunftszeit (Arrival Time) Zeitpunkt an dem eine Task dem Betriebssystem bekannt gemacht wird die Taskverwaltung nimmt die Task in die Taskliste und setzt sie in den Zustand ruhend

ri Anforderungszeit (Request Time) Die Task bewirbt sich bei der Taskverwaltung um den Prozessor

si Startzeit (Start Time) die Task erhaumllt den Prozessor zugeteilt

ci Beendigungszeit (Completion Time) Die Task hat ihre Aufgabe erledigt und kehrt in den Zustand ruhend zuruumlck

di Zeitschranke (Deadline) Zeitpunkt an dem die Taskausfuumlhrung spaumltestens beendet sein muss Die Zeitschranke kann hart fest oder weich sein

pi Periode (Period) Zeitdauer kennzeichnet die Wiederholungsrate bei periodischen Tasks sie ergibt sich aus der Zeitdifferenz zwischen zwei aufeinander folgenden Anforderungszeiten einer Task

ei Ausfuumlhrungszeit (Execution Time) Zeitdauer die eine Task zur Ausfuumlhrung ihrer Aufgabe benoumltigt wenn sie sich im Zustand laufend befindet Eine Variante ist die maximale Ausfuumlhrungszeit (worst case execution time = WCET) eine obere Schranke der Ausfuumlhrungszeit die in keinem Fall uumlberschritten werden darf

li Spielraum (Laxity) verbleibende Restzeit zwischen Beendigungszeit und Zeitschranke

ji Reaktionszeit (Reaction Time Release Jitter) Zeitraum kennzeichnet die Verzoumlgerung zwischen Anforderung und dem Start der Ausfuumlhrung

Seite 26

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Uumlbungsfragen (Vorl Uni Stuttgart)

1048709 Eine Task im Zustand ldquorunnablerdquo wird momentan ausgefuumlhrt

1048709 Ein Task-Zustand kann direkt von ldquorunningrdquo zu ldquodormantrdquo wechseln

1048709 Eine Task im Zustand ldquosuspendedrdquo kann direkt in den Zustand ldquorunningrdquo wechseln

1048709 Eine Task im Zustand ldquodormantrdquo ist nicht bereit da Zeit- oder andere Bedingungen nicht

erfuumlllt sind

1048709 Eine Task im Zustand ldquosuspendedrdquo wartet auf das Auftreten eines Events

Seite 24

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

t

ai

ruhend

ablaufwillig

laufend

blockiert

Parameter zur Beschreibung des Zeitverhaltens von Tasks

risi ci

di

pi

ji liei

ai Ankunftszeit

ri Anforderungszeit

si Startzeit

ci Beendigungszeit

di Zeitschranke (Deadline)

pi Periode

ei Ausfuumlhrungszeit

li Spielraum (Laxity)

ji Reaktionszeit

Task-zustaumlnde

Ankunftszeit Task wird in Taskliste aufgenommen

Anforderungszeit Ereignis tritt ein Task wird ablaufwilligStartzeit Task erhaumllt

erstmalig die CPU zugeteilt

Beendigungszeit Task hat Aufgabe erledigt und ruht wieder

Deadline Zeit zu der die Task spaumltestens beendet sein muss

Ausfuumlhrungszeit Rechenzeit der Task (ohne Wartezeiten)

Periode Zeitdifferenz zwischen aufeinander folgenden Anforderungen

Spielraum Restzeit zwischen Beendigung und Deadline

Reaktionszeit Zeit zwischen Anfor-derung und Start der Ausfuumlhrung

Seite 25

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

ai Ankunftszeit (Arrival Time) Zeitpunkt an dem eine Task dem Betriebssystem bekannt gemacht wird die Taskverwaltung nimmt die Task in die Taskliste und setzt sie in den Zustand ruhend

ri Anforderungszeit (Request Time) Die Task bewirbt sich bei der Taskverwaltung um den Prozessor

si Startzeit (Start Time) die Task erhaumllt den Prozessor zugeteilt

ci Beendigungszeit (Completion Time) Die Task hat ihre Aufgabe erledigt und kehrt in den Zustand ruhend zuruumlck

di Zeitschranke (Deadline) Zeitpunkt an dem die Taskausfuumlhrung spaumltestens beendet sein muss Die Zeitschranke kann hart fest oder weich sein

pi Periode (Period) Zeitdauer kennzeichnet die Wiederholungsrate bei periodischen Tasks sie ergibt sich aus der Zeitdifferenz zwischen zwei aufeinander folgenden Anforderungszeiten einer Task

ei Ausfuumlhrungszeit (Execution Time) Zeitdauer die eine Task zur Ausfuumlhrung ihrer Aufgabe benoumltigt wenn sie sich im Zustand laufend befindet Eine Variante ist die maximale Ausfuumlhrungszeit (worst case execution time = WCET) eine obere Schranke der Ausfuumlhrungszeit die in keinem Fall uumlberschritten werden darf

li Spielraum (Laxity) verbleibende Restzeit zwischen Beendigungszeit und Zeitschranke

ji Reaktionszeit (Reaction Time Release Jitter) Zeitraum kennzeichnet die Verzoumlgerung zwischen Anforderung und dem Start der Ausfuumlhrung

Seite 26

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Uumlbungsfragen (Vorl Uni Stuttgart)

1048709 Eine Task im Zustand ldquorunnablerdquo wird momentan ausgefuumlhrt

1048709 Ein Task-Zustand kann direkt von ldquorunningrdquo zu ldquodormantrdquo wechseln

1048709 Eine Task im Zustand ldquosuspendedrdquo kann direkt in den Zustand ldquorunningrdquo wechseln

1048709 Eine Task im Zustand ldquodormantrdquo ist nicht bereit da Zeit- oder andere Bedingungen nicht

erfuumlllt sind

1048709 Eine Task im Zustand ldquosuspendedrdquo wartet auf das Auftreten eines Events

Seite 25

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

ai Ankunftszeit (Arrival Time) Zeitpunkt an dem eine Task dem Betriebssystem bekannt gemacht wird die Taskverwaltung nimmt die Task in die Taskliste und setzt sie in den Zustand ruhend

ri Anforderungszeit (Request Time) Die Task bewirbt sich bei der Taskverwaltung um den Prozessor

si Startzeit (Start Time) die Task erhaumllt den Prozessor zugeteilt

ci Beendigungszeit (Completion Time) Die Task hat ihre Aufgabe erledigt und kehrt in den Zustand ruhend zuruumlck

di Zeitschranke (Deadline) Zeitpunkt an dem die Taskausfuumlhrung spaumltestens beendet sein muss Die Zeitschranke kann hart fest oder weich sein

pi Periode (Period) Zeitdauer kennzeichnet die Wiederholungsrate bei periodischen Tasks sie ergibt sich aus der Zeitdifferenz zwischen zwei aufeinander folgenden Anforderungszeiten einer Task

ei Ausfuumlhrungszeit (Execution Time) Zeitdauer die eine Task zur Ausfuumlhrung ihrer Aufgabe benoumltigt wenn sie sich im Zustand laufend befindet Eine Variante ist die maximale Ausfuumlhrungszeit (worst case execution time = WCET) eine obere Schranke der Ausfuumlhrungszeit die in keinem Fall uumlberschritten werden darf

li Spielraum (Laxity) verbleibende Restzeit zwischen Beendigungszeit und Zeitschranke

ji Reaktionszeit (Reaction Time Release Jitter) Zeitraum kennzeichnet die Verzoumlgerung zwischen Anforderung und dem Start der Ausfuumlhrung

Seite 26

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Uumlbungsfragen (Vorl Uni Stuttgart)

1048709 Eine Task im Zustand ldquorunnablerdquo wird momentan ausgefuumlhrt

1048709 Ein Task-Zustand kann direkt von ldquorunningrdquo zu ldquodormantrdquo wechseln

1048709 Eine Task im Zustand ldquosuspendedrdquo kann direkt in den Zustand ldquorunningrdquo wechseln

1048709 Eine Task im Zustand ldquodormantrdquo ist nicht bereit da Zeit- oder andere Bedingungen nicht

erfuumlllt sind

1048709 Eine Task im Zustand ldquosuspendedrdquo wartet auf das Auftreten eines Events

Seite 26

DHBW Stuttgart Studiengang Elektrotechnik 5 HJ Vorlesung Realzeitsysteme Sep 2012

4) Task-Verwaltung

Uumlbungsfragen (Vorl Uni Stuttgart)

1048709 Eine Task im Zustand ldquorunnablerdquo wird momentan ausgefuumlhrt

1048709 Ein Task-Zustand kann direkt von ldquorunningrdquo zu ldquodormantrdquo wechseln

1048709 Eine Task im Zustand ldquosuspendedrdquo kann direkt in den Zustand ldquorunningrdquo wechseln

1048709 Eine Task im Zustand ldquodormantrdquo ist nicht bereit da Zeit- oder andere Bedingungen nicht

erfuumlllt sind

1048709 Eine Task im Zustand ldquosuspendedrdquo wartet auf das Auftreten eines Events