Betriebssystembau (BSB): 01

Betriebssystembau (BSB)
7. Übung
http://ess.cs.tu-dortmund.de/DE/Teaching/WS2014/BSB/
Olaf Spinczyk
[email protected]
http://ess.cs.tu-dortmund.de/~os
AG Eingebettete Systemsoftware
Informatik 12, TU Dortmund
Agenda
●
Nachtrag: Die unterbrechungstransparente Queue
●
Korrektheitsbeweis mit SPIN
●
Vorstellung Aufgabe 7
13.01.15
Betriebssystembau: 7. Übung
2
Agenda
●
Nachtrag: Die unterbrechungstransparente Queue
●
Korrektheitsbeweis mit SPIN
●
Vorstellung Aufgabe 7
13.01.15
Betriebssystembau: 7. Übung
3
Knifflige Zeiger: Queue in Aufgabe 3
●
Queue-Elemente erben von Chain
–
●
Sie erben damit auch einen Zeiger
auf das nächste Element
Ein Queue-Objekte enthält
class Chain {
public:
Chain* next;
};
–
einen Zeiger auf das erste Element
–
einen Zeiger auf einen Zeiger namens 'tail'!?
class Queue {
Chain* head;
Chain** tail;
public:
Queue () { head = 0; tail = &head; }
void enqueue (Chain* item);
Chain* dequeue ();
void remove (Chain*);
};
13.01.15
Betriebssystembau: 7. Übung
4
Knifflige Zeiger: Queue in Aufgabe 3
●
'tail' ist ein Zeiger auf den 'next' Zeiger im letzten Element
–
Das macht das Anhängen (enqueue) sehr einfach:
q
q.enqueue(&e1)
item->next = NULL;
NULL
*tail = item;
q.enqueue(&e2)
13.01.15
e2
'b'
NULL
?
'a'
'b'
NULL
?
'a'
'b'
NULL
?
'a'
'b'
...
tail = &item->next;
e1
'a'
item->next = NULL;
*tail = item;
tail = &item->next;
NULL
Betriebssystembau: 7. Übung
5
Unterbrechungstransparente Queue
An der Tafel bzw. in ...
[1] F. Schön, W. Schröder-Preikschat, O. Spinczyk, and U.
Spinczyk. On Interrupt-Transparent Synchronization in an
Embedded Object-Oriented Operating System. In The Third
IEEE International Symposium on Object-Oriented
Real-Time Distributed Computing (ISORC 2000), pages 270277, Newport Beach, California, March 15-17,
2000. IEEE Computer Society. ISBN 0-7695-0607-0.
13.01.15
Betriebssystembau: 7. Übung
6
Agenda
●
Nachtrag: Die unterbrechungstransparente Queue
●
Korrektheitsbeweis mit SPIN
●
Vorstellung Aufgabe 7
13.01.15
Betriebssystembau: 7. Übung
7
Model Checking (mit SPIN)
●
●
Kein deduktiver mathematischer Beweis!
Korrektheitsbeweis durch vollständige Analyse des
Zustandsraumes
–
Zustandsraum muss endlich sein
●
–
Komplexitätsgrenzen für große Systeme/Algorithmen
●
●
Feste Anzahl von Prozessen, Wertebereiche, Speicher, …
Verifikation eines vereinfachten Modells (→ Model Checking)
Grundprinzip
–
Modell und negierte Korrektheitsanforderungen → Endliche Automaten
–
Suche: Eingabestring, den beide Automaten akzeptieren
(Gegenbeispiel)
13.01.15
Betriebssystembau: 7. Übung
8
Model Checking mit SPIN
●
Modellierung des Systems/Algorithmus' in PROMELA
–
Sehr einfache/reduzierte Sprache ähnlich zu C/Java
●
●
Keine Zeiger, Referenzen, Funktionen, Klassen, Generics, …
–
Abstraktion auf das Wesentliche → Minimale Zustandsautomaten
–
Achtung: Modell ⇔ Implementierung ?
Spezifikation der Korrektheitsanforderungen
–
assert(...) Anweisungen (lokal)
–
Lineare temporale Logik (global)
13.01.15
Betriebssystembau: 7. Übung
9
Beispiel: Gegenseitiger Ausschluss
// Peterson's solution to the mutual exclusion problem (1981)
bool turn, flag[2];
// the shared variables, booleans
byte ncrit;
// nr of procs in critical section
active [2] proctype user() { // two processes
assert(_pid == 0 || _pid == 1);
again:
flag[_pid] = 1;
turn = _pid;
(flag[1 - _pid] == 0 || turn == 1 - _pid);
ncrit++;
assert(ncrit == 1);
ncrit--;
}
//
//
//
//
13.01.15
// critical section
flag[_pid] = 0;
goto again
analysis:
$ spin -a peterson.pml
$ gcc -o pan pan.c
$ ./pan
Betriebssystembau: 7. Übung
Boolsche Ausdrücke
(ohne if) blockieren
bis die genannte
Bedingung eintrifft
10
Agenda
●
Nachtrag: Die unterbrechungstransparente Queue
●
Korrektheitsbeweis mit SPIN
●
Vorstellung Aufgabe 7
13.01.15
Betriebssystembau: 7. Übung
11