Select Git revision
bs-20160404.tex
Forked from
Peter Gerwinski / bs
This fork has diverged from the upstream repository.
bs-20160404.tex 38.31 KiB
% bs-20160404.pdf - Lecture Slides on Operating Systems
% Copyright (C) 2014, 2015, 2016 Peter Gerwinski
%
% This document is free software: you can redistribute it and/or
% modify it either under the terms of the Creative Commons
% Attribution-ShareAlike 3.0 License, or under the terms of the
% GNU General Public License as published by the Free Software
% Foundation, either version 3 of the License, or (at your option)
% any later version.
%
% This document is distributed in the hope that it will be useful,
% but WITHOUT ANY WARRANTY; without even the implied warranty of
% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
% GNU General Public License for more details.
%
% You should have received a copy of the GNU General Public License
% along with this document. If not, see <http://www.gnu.org/licenses/>.
%
% You should have received a copy of the Creative Commons
% Attribution-ShareAlike 3.0 Unported License along with this
% document. If not, see <http://creativecommons.org/licenses/>.
\documentclass[10pt,t]{beamer}
\usepackage{pgslides}
\usepackage{rotating}
\usepackage{pdftricks}
\usepackage[obeyfamily=false,mathrm=mathsf,textrm=sffamily]{siunitx}
\usepackage{eurosym}
\begin{psinputs}
\usepackage[latin1]{inputenc}
\usepackage[german]{babel}
\usepackage[T1]{fontenc}
\usepackage{helvet}
\renewcommand*\familydefault{\sfdefault}
\usepackage{pstricks}
\psset{unit=1cm}
\end{psinputs}
\title{Treiberentwicklung,\\[\medskipamount]Echtzeit- und Betriebssysteme}
\author{Prof.\ Dr.\ Peter Gerwinski}
\date{4.\ April 2016}
\begin{document}
\newlength{\normalpdfpageheight}
\setlength{\normalpdfpageheight}{\pdfpageheight}
\maketitleframe
\sectionnonumber{Treiberentwicklung, Echtzeit- und Betriebssysteme}
%\begin{frame}
%
% \showsectionnonumber
%
% \begin{itemize}
% \item[\textbf{1}] \textbf{Einfhrung}
% \item[\textbf{\dots}]
% \end{itemize}
%
%\end{frame}
\section{Einfhrung}
\begin{frame}
\showsection
Was ist ein Betriebssystem?
\pause
\strut\hfill
\begin{picture}(0,0)
\put(0,1.5){\makebox(0,0)[tr]{\includegraphics[height=7cm]{Operating_system_placement-de.pdf}}}
\end{picture}
\begin{itemize}
\item
Software, die zwischen Hardware\\
und Anwendung vermittelt
\pause\bigskip
\item
Mikro-Controller:\\
Anwendung greift \emph{direkt\/} auf Hardware zu
\pause\bigskip
\item
Eingebettetes System:\\
Anwendung startet automatisch
\item
Arbeitsplatz-Computer:
\newterm{Oberflche (Shell)}\\
Benutzer whlt Anwendung aus
\pause\bigskip
\item
Ressourcen-Verwaltung
\end{itemize}
\end{frame}
\begin{frame}
\showsection
Was gehrt zum Betriebssystem?
\strut\hfill
\begin{picture}(0,0)
\thicklines
\put(-3,0){\vector(0,-1){7}}
\put(-2.8,-0.5){\makebox(0,0)[l]{Ja, klar!}}
\put(-2.8,-6.5){\makebox(0,0)[l]{Hmm\,\dots\ vielleicht.}}
\end{picture}
\begin{itemize}
\item
Betriebssystemkern: \newterm{Kernel}
\item
Benutzeroberflche: \newterm{Shell}\\
text- oder grafikorientiert\\
(im engeren Sinne: Kommandozeile)
\item
Werkzeuge zur Verwaltung von Ressourcen\\
(z.\,B.\ Festplatten formatieren)
\item
Graphische Benutzeroberflche: \newterm{GUI}
\item
Texteditor
\item
Entwicklungswerkzeuge (Compiler usw.),\\
Skriptsprachen
\item
Internet-Software: Web-Browser, E-Mail-Client usw.
\item
Multimedia-Software
\item
Bro-Anwendungssoftware
\end{itemize}
\end{frame}
\begin{frame}
\showsection
In dieser Lehrveranstaltung:
\begin{itemize}
\item
Treiberentwicklung\\
wie in \emph{Angewandte Informatik\/} (5.\ Sem.), nur "`grer"'
\item
Echtzeitsysteme\\
wie in \emph{Vertiefung Systemtechnik\/} (7.\ Sem.), nur "`grer"'
\item
neu: Betriebssysteme
\end{itemize}
\pause
\bigskip
Statt Klausur: Projektaufgabe, z.\,B.:
\begin{itemize}
\item
neuartiger Treiber (z.\,B.\ fr neuartige Hardware)
\item
neuartige Echtzeit-Funktionalitt
\item
Sonstiges
\end{itemize}
\pause
\bigskip
Wiederholung:
\begin{itemize}
\item
Hardwarenahe Programmierung
\item
Theorie der Echtzeit-Systeme
\item[\textbf{?}]
Sonstiges
\end{itemize}
\end{frame}
\section{Der Bootvorgang}
\begin{frame}
\showsection
\begin{itemize}
\item
Rechner eingschalten\\
\textarrow\ Programm im Festspeicher (ROM) startet
\item
Mikro-Controller: Das war's schon.\\
Arbeitsplatzrechner: Weiter geht's.
\item
Programm spricht Datentrger an,\\
ldt und startet greres Programm,\\
kann mehr Datentrger ansprechen
\item
greres Programm ldt noch greres Programm
\item
\dots
\item
Zuletzt: Programm starten, das mit dem Benutzer interagiert
\bigskip
\item abstraktes Beispiel: Bootloader, Kernel, Anmelde-Proze
\item
konkretes Beispiel: Linux\\
GRUB-Stages, Kernel mit initrd, init, getty und/oder Display-Manager
\end{itemize}
\end{frame}
\setcounter{section}{3}
\section{Echtzeit}
\subsection{Was ist Echtzeit?}
\begin{frame}
\showsection
\vspace{-\smallskipamount}
\showsubsection
\begin{itemize}
\item
Animation in Echtzeit:\\
schnelle Berechnung anstatt Wiedergabe einer Aufzeichnung
\item
Fantasy-Rollenspiel in Echtzeit:\\
Der Zeitverlauf der Spielwelt entspricht dem der realen Welt.
\item
Datenverarbeitung in Echtzeit:\\
Die Daten werden so schnell verarbeitet, wie sie anfallen.
\item
speziell: Echtzeit-Steuerung von Maschinen:\\
Die Berechnung kann mit den physikalischen Vorgngen schritthalten.
\smallskip
\arrowitem
"`Schnell genug."'
\end{itemize}
\end{frame}
\begin{frame}
\showsubsection
"`Schnell genug."' -- "`Und wenn nicht?"'
\begin{itemize}
\item
"`Ganz schlecht."' \textarrow\ \newterm{harte Echtzeit}\\[2pt]
rechtzeitiges Ergebnis funktionsentscheidend
\smallskip
\item
"`Unschn."' \textarrow\ \newterm{weiche Echtzeit}\\[2pt]
versptetes Ergebnis qualittsmindernd
\begin{itemize}
\baselineskip14pt\par
\item
verwenden und Verzgerung in Kauf nehmen
\item
verwerfen und Ausfall in Kauf nehmen
\end{itemize}
\smallskip
\item
"`Es gibt keinen festen Termin. Mglichst schnell halt."'\\[2pt]
\textarrow\ \newterm{keine Echtzeit}
\end{itemize}
\end{frame}
\begin{frame}[fragile]
\showsubsection
Das Problem:
\vspace{-\bigskipamount}
\begin{center}
% \begin{picture}(6,2)
% \put(3,2){\makebox(0,0)[t]{Harte Echtzeitanforderungen}}
% \put(3,0){\makebox(0,0)[b]{Ressourcen optimal nutzen}}
% \put(2.75,0.875){\vector(1,3){0.25}}
% \put(2.75,0.875){\line(2,1){0.5}}
% \put(3.25,1.125){\vector(-1,-3){0.25}}
% \end{picture}
\begin{pdfpic}
\begin{pspicture}(6,2)
\put(3,2){\makebox(0,0)[t]{Harte Echtzeitanforderungen}}
\put(3,0){\makebox(0,0)[b]{Ressourcen optimal nutzen}}
\psline[arrows=<->](3,0.4)(3.2,1.125)(2.8,0.875)(3,1.6)
\end{pspicture}
\end{pdfpic}
\end{center}
Beispiel:
\begin{itemize}
\item
Eine Motorsteuerung bentigt alle \SI{2000}{\mics} einen Steuerimpuls,\\
dessen Berechnung maximal \SI{10}{\mics} dauert.
\item
Entweder: Der Steuer-Computer macht noch andere Dinge.\\
\textarrow\ Risiko der Zeitberschreitung
\item
Oder: Der Steuer-Computer macht nichts anderes.\\
\textarrow\ Verschwendung von Rechenzeit\\
{\color{red}\textarrow\ Na und?}
\end{itemize}
\end{frame}
\begin{frame}[fragile]
\showsubsection
Das Problem:
\vspace{-\bigskipamount}
\begin{center}
\begin{pdfpic}
\begin{pspicture}(6,2)
\put(3,2){\makebox(0,0)[t]{Harte Echtzeitanforderungen}}
\put(3,0){\makebox(0,0)[b]{Ressourcen optimal nutzen}}
\psline[arrows=<->](3,0.4)(3.2,1.125)(2.8,0.875)(3,1.6)
\end{pspicture}
\end{pdfpic}
\end{center}
\medskip
{\large\color{structure}\textbf{"`Verschwendung von Rechenzeit -- na und?"'}}
\medskip
Groe Stckzahlen
\begin{itemize}
\item
138\,000 Toyota Prius V von Mai 2011 bis April 2012
\end{itemize}
\medskip
Wertvolle Ressourcen
\begin{itemize}
\item
Fhigkeiten einer Raumsonde optimieren
% (Marsumlaufbahn: ab ca.~127\,000 Euro pro kg)
% 70000000 / 550000 = 127._27
% http://www.bernd-leitenberger.de/blog/2009/09/29/reduktion-der-kosten-von-planetenmissionen/
% \only<.(1)>{\\[\bigskipamount]\strut\hfill\makebox(0,0)[r]{\includegraphics[height=3.5cm]{curiosity.jpg}}\vspace*{-1cm}}
\item
Implantat: Platz- und Stromverbrauch minimieren
% \only<.(1)>{\\[\smallskipamount]\strut\hfill\makebox(0,0)[r]{\includegraphics[height=3.4cm]{herzschrittmacher.jpg}}\vspace*{-1cm}}
\end{itemize}
\bigskip
\textarrow\ {\large\color{structure}\textbf{Echtzeitprogrammierung}}\\[2pt]
\strut \phantom{\textarrow} Echtzeitanforderungen erfllen, ohne Ressourcen zu verschwenden
\end{frame}
\subsection{Multitasking}
\begin{frame}
\showsection
\showsubsection
\begin{minipage}[t]{6cm}
Qualittssicherung beim Multitasking
\begin{itemize}
\item
Verschiedene Anforderungen:
\newterm{Latenz\/} vs.\ \newterm{Jitter\/}\\
vs.\ \newterm{Durchsatz}
\item
Ressourcen reservieren:\\
\newterm{Mutexe}
(= spezielle \newterm{Semaphore\/})\\
\strut
\item
Verschiedene Methoden\\
der Priorisierung\\
\strut
\item
Umgehung der Probleme durch
speziell geschriebene Software\\
(MultiWii, RP6, \dots)
\end{itemize}
\end{minipage}
\hfill
\begin{minipage}[t]{6.2cm}
Qualittssicherung fr Netzwerke:
\begin{itemize}
\item
Verschiedene Anforderungen:
\newterm{Latenz\/} vs.\ \newterm{Jitter\/} vs.\ \newterm{Verluste\/}\\vs.\ \newterm{Durchsatz}
\item
Ressourcen reservieren:\\
\newterm{IntServ} mit \newterm{Resource Reservation Protocol (RSVP)}
\item
Klassifizierung und Priorisierung:
\newterm{DiffServ} mit Type-of-Service-Bits (IPv4)
bzw.\ Traffic-Class-Bits (IPv6) im IP-Header
\item
Eigenes Protokoll (Telefondienste):\\
\newterm{Asynchronous Transfer Mode (ATM)}
\end{itemize}
\end{minipage}
\end{frame}
% Aufgabe: Anwendungsarten im MultiWii- und RP6-Code identifizieren
% evtl. Aufgabe: Warte-Problem
% Aufgabe: Wie lsen bekannte Multitasking-Betriebssysteme
% das o.a. Zuteilungsproblem?
% Danach: Semaphoren, Mutexe, Spinlocks
% Priorisierungsmethoden und -probleme
\subsectionnonumber{Beispiele fr Multitasking}
\begin{frame}
\showsubsectionnonumber
Quadrocopter-Steuerung \emph{MultiWii}
\begin{itemize}
\item
Konfiguration durch bedingte Compilierung (Prprozessor)
\item
In der Hauptschleife wird 50mal pro Sekunde der RC-Task aufgerufen,\\
ansonsten zyklisch einer von bis zu 5 weiteren Tasks.
\end{itemize}
RP6-Steuerung
\begin{itemize}
\item
Konfiguration durch bedingte Compilierung (Prprozessor)
\item
Lichtschranken an Encoder-Scheiben lsen bei Bewegung Interrupts aus.\\
Die Interrupt-Handler zhlen Variable hoch.
\item
10000mal pro Sekunde: Timer-Interrupt\\
verschiedene Tasks werden unterschiedlich hufig aufgerufen
\item
Nebenbei: 1 Benutzerprogramm
\end{itemize}
Linux 0.01
\begin{itemize}
\item
Timer-Interrupt:\only<2->{ Zhler des aktuellen Tasks wird dekrementiert;}\\
Task mit hchstem Zhler bekommt Rechenzeit.
\item
Wenn es keinen laufbereiten Task mit positivem Zhler gibt,\\
bekommen alle Tasks gem ihrer Prioritt neue Zhler zugewiesen.
\item<3->
\emph{keine\/} harte Echtzeit
% Aufgabe: Wo wird der Zhler heruntergezhlt?
\end{itemize}
\end{frame}
\iffalse
\subsectionnonumber{Zombies}
\begin{frame}
\showsubsectionnonumber
\pause
Wikipedia:
\begin{quote}
Als Zombie wird die fiktive Figur eines zum Leben erweckten
Toten (Untoter) oder eines seiner Seele beraubten, willenlosen
Wesens bezeichnet. Der Begriff leitet sich von dem Wort nzmbe
aus der zentralafrikanischen Sprache Kimbundu ab und bezeichnet dort ursprnglich einen Totengeist.
\end{quote}
\bigskip
\pause
Ein Zombie-Proze ist bereits beendet ("`tot"'),\\
bekommt keine Rechenzeit mehr ("`seiner Seele beraubt"'),\\
hat alle belegten Ressourcen wieder freigegeben ("`willenlos"'),\\
wird aber noch in der Prozeliste gefhrt ("`untot"').
\begin{itemize}
\pause
\item
Warum?
\textarrow\
Ein anderer Proze (Elternproze) wartet noch auf den
Rckgabewert des beendeten Prozesses.
\pause
\item
Schadet das?
\textarrow\
Nein.
\pause
\item
Aber?
\textarrow\
Wenn sich Zombie-Prozesse anhufen, deutet dies auf einen
Proze hin, der andere Prozesse erzeugt und anschlieend "`hngt"'.
\pause
\item
Beispiel:
Datentrger entfernt, zugreifender Proze "`hngt"'.\\
\textarrow\
Tochterprozesse werden zu Zombies.
\end{itemize}
\end{frame}
\fi
\subsection{Ressourcen}
\begin{frame}
\showsection
\showsubsection
Ressourcen reservieren
\begin{itemize}
\item
\newterm{Semaphor}\\
gemeinsame Variable mehrerer Prozesse\\
zur Regelung des Zugriffs auf eine Ressource\\[\smallskipamount]
Ressource belegt \textarrow\ Kontextwechsel
\begin{onlyenv}<1>
\par\medskip
griechisch: \emph{sema\/} -- Zeichen, \emph{pherein\/} -- tragen\\
"`Eisenbahnsignal"'
\vspace*{-3cm}
\end{onlyenv}
\pause
\medskip
\item
\newterm{Mutex}\\
Mechanismus, damit immer nur ein Proze gleichzeitig\\
auf eine Ressource zugreifen kann
\begin{onlyenv}<2>
\par\medskip
englisch: \emph{mutual exclusion\/} -- wechselseitiger Ausschlu\\
spezieller binrer Semaphor: nur "`Besitzer"' darf freigeben\\ % allgemein: auch jemand anderer drfte freigeben
\vspace*{-3cm}
\end{onlyenv}
\pause
\medskip
\item
\newterm{Spinlock} (\emph{busy waiting\/})\\
leichtgewichtige Alternative zu Kontextwechsel
\begin{onlyenv}<3>
\par\medskip
englisch: \emph{spin\/} -- rotieren, \emph{lock\/} Sperre\\
\emph{busy waiting} auf etwas Schnelles, z.\,B.\ auf einen Semaphor\\[\medskipamount]
Hardware-Untersttzung:
Prfen, ob Variable bestimmten Wert hat;\\
wenn ja, auf anderen Wert setzen; andere Prozessoren solange anhalten
\vspace*{-3cm}
\end{onlyenv}
\pause
\medskip
\item
\newterm{Kritischer Abschnitt -- critical section}\\
Programmabschnitt zwischen Reservierung\\
und Freigabe einer Ressource\\
\textarrow\ sollte immer so kurz wie mglich sein
\end{itemize}
\end{frame}
\begin{frame}
\showsection
\showsubsection
Ressourcen reservieren: Beispiele
\begin{itemize}
\item
\newterm{Semaphor}\\
\file{linux-3.7-rc1/kernel/semaphor.c}\\
\file{linux-3.7-rc1/drivers/usb/core/file.c}
\medskip
\item
\newterm{Mutex}\\
\file{linux-3.7-rc1/kernel/mutex.c}\\
\file{linux-3.7-rc1/drivers/usb/serial/usb-serial.c}
\medskip
\item
\newterm{Spinlock}\\
\file{linux-3.7-rc1/kernel/spinlock.c}\\
\file{linux-3.7-rc1/kernel/semaphor.c},
\file{linux-3.7-rc1/kernel/mutex.c}
\end{itemize}
% Aufgabe: Anwendungsarten im MultiWii- und RP6-Code identifizieren
% evtl. Aufgabe: Warte-Problem
% Aufgabe: Wie lsen bekannte Multitasking-Betriebssysteme
% das o.a. Zuteilungsproblem?
% Danach: Semaphoren, Mutexe, Spinlocks
% Priorisierungsmethoden und -probleme
% Festplatten: completely fair queueing
% cat /sys/block/sdc/queue/scheduler
% "noop" hat sich fr SVG gelohnt
% Virtualisierung + Kernel-Threads + Multiprozessorsystem = Chaos
\end{frame}
\begin{frame}[fragile]
\textbf{Beispiel:}
\lstinline{usb_serial_get_by_index()} -- serielle Schnittstelle reservieren
Datei \file{linux-3.7-rc1/drivers/usb/serial/usb-serial.c}, ab Zeile 62
\medskip
\begin{lstlisting}
struct usb_serial *usb_serial_get_by_index (unsigned index)
{
struct usb_serial *serial;
mutex_lock (&table_lock);
serial = serial_table[index];
if (serial)
{
mutex_lock (&serial->disc_mutex);
if (serial->disconnected)
{
mutex_unlock (&serial->disc_mutex);
serial = NULL;
}
else
kref_get (&serial->kref);
}
mutex_unlock (&table_lock);
return serial;
}
\end{lstlisting}
\begin{picture}(0,0)
\color{red}
\put(5.1,6.85){\vector(-1,0){0.5}}
\put(5.2,6.85){\makebox(0,0)[l]{exklusiven Zugriff auf Tabelle sichern}}
\put(5.4,1.35){\vector(-1,0){0.5}}
\put(5.5,1.35){\makebox(0,0)[l]{\shortstack[l]{exklusiven Zugriff auf Tabelle\\wieder freigeben}}}
\end{picture}
\end{frame}
\setlength{\pdfpageheight}{48cm}
\begin{frame}[fragile]
\lstinline{mutex_lock()} -- Ressource beanspruchen, notfalls warten
Datei \file{linux-3.7-rc1/drivers/usb/serial/usb-serial.c}, ab Zeile 62
\medskip
\begin{lstlisting}
void __sched mutex_lock (struct mutex *lock)
{
might_sleep ();
__mutex_fastpath_lock (&lock->count, __mutex_lock_slowpath);
mutex_set_owner (lock);
}
\end{lstlisting}
\begin{picture}(0,0)
\color{red}
\put(11.6,1.35){\line(-1,0){1}}
\put(11.6,1.35){\line(0,-1){2.45}}
\put(11.6,-1.10){\vector(-1,0){2.0}}
\end{picture}
\bigskip
Datei \file{linux-3.7-rc1/arch/x86/include/asm/mutex\_32.h}, ab Zeile 24
Macro-Definition fr \lstinline{__mutex_fastpath_lock} (expandiert)
\medskip
Assembler:
\begin{lstlisting}[language={[x86masm]Assembler}]
lock dec (lock->count)
jns 1
call __mutex_lock_slowpath
1:
\end{lstlisting}
\begin{picture}(0,0)
\color{red}
\put(9,0.95){\line(-1,0){3.5}}
\put(9,0.95){\line(0,-1){2.5}}
\put(9.0,-1.55){\vector(-1,0){1.0}}
\end{picture}
\bigskip
Datei \file{linux-3.7-rc1/kernel/mutex.c}, ab Zeile 398
\medskip
\begin{lstlisting}
static __used noinline void __sched
__mutex_lock_slowpath (atomic_t *lock_count)
{
struct mutex *lock = container_of (lock_count, struct mutex, count);
__mutex_lock_common (lock, TASK_UNINTERRUPTIBLE, 0,
NULL, _RET_IP_);
}
\end{lstlisting}
\begin{picture}(0,0)
\color{red}
\put(11.0,1.40){\line(-1,0){1.0}}
\put(11.0,1.40){\vector(0,-1){2.5}}
\end{picture}
\bigskip
Datei \file{linux-3.7-rc1/kernel/mutex.c}, ab Zeile 132
\medskip
\begin{lstlisting}
static inline int __sched
__mutex_lock_common (struct mutex *lock, long state, unsigned int subclass,
struct lockdep_map *nest_lock, unsigned long ip)
{
struct task_struct *task = current;
struct mutex_waiter waiter;
unsigned long flags;
preempt_disable ();
mutex_acquire_nest (&lock->dep_map, subclass, 0, nest_lock, ip);
/* ... */
spin_lock_mutex (&lock->wait_lock, flags);
debug_mutex_lock_common (lock, &waiter);
debug_mutex_add_waiter (lock, &waiter, task_thread_info (task));
/* add waiting tasks to the end of the waitqueue (FIFO): */
list_add_tail (&waiter.list, &lock->wait_list);
waiter.task = task;
if (atomic_xchg (&lock->count, -1) == 1)
goto done;
lock_contended (&lock->dep_map, ip);
for (;;)
{
/*
* Lets try to take the lock again - this is needed even if
* we get here for the first time (shortly after failing to
* acquire the lock), to make sure that we get a wakeup once
* it's unlocked. Later on, if we sleep, this is the
* operation that gives us the lock. We xchg it to -1, so
* that when we release the lock, we properly wake up the
* other waiters:
*/
if (atomic_xchg (&lock->count, -1) == 1)
break;
/*
* got a signal? (This code gets eliminated in the
* TASK_UNINTERRUPTIBLE case.)
*/
if (unlikely (signal_pending_state (state, task)))
{
mutex_remove_waiter (lock, &waiter, task_thread_info (task));
mutex_release (&lock->dep_map, 1, ip);
spin_unlock_mutex (&lock->wait_lock, flags);
debug_mutex_free_waiter (&waiter);
preempt_enable ();
return -EINTR;
}
__set_task_state (task, state);
/* didn't get the lock, go to sleep: */
spin_unlock_mutex (&lock->wait_lock, flags);
schedule_preempt_disabled ();
spin_lock_mutex (&lock->wait_lock, flags);
}
done:
lock_acquired (&lock->dep_map, ip);
/* got the lock - rejoice! */
mutex_remove_waiter (lock, &waiter, current_thread_info ());
mutex_set_owner (lock);
/* set it to 0 if there are no waiters left: */
if (likely (list_empty (&lock->wait_list)))
atomic_set (&lock->count, 0);
spin_unlock_mutex (&lock->wait_lock, flags);
debug_mutex_free_waiter (&waiter);
preempt_enable ();
return 0;
}
\end{lstlisting}
\begin{picture}(0,0)
\color{red}
\put(7.9,28.3){\vector(-1,0){0.5}}
\put(8.0,28.3){\makebox(0,0)[l]{\shortstack[l]{exklusiven Zugriff\\auf Mutex sichern}}}
\put(7.4,2.3){\vector(-1,1){0.4}}
\put(7.5,2.0){\makebox(0,0)[l]{\shortstack[l]{exklusiven Zugriff auf Mutex\\wieder freigeben}}}
\end{picture}
\end{frame}
\setlength{\pdfpageheight}{40.5cm}
\begin{frame}[fragile]
\lstinline{spin_lock_mutex()} -- Mutex beanspruchen, notfalls \emph{busy waiting}
Datei \file{linux-3.7-rc1/kernel/mutex.h}, ab Zeile 12
\medskip
\begin{lstlisting}
#define spin_lock_mutex(lock, flags) \
do \
{ \
spin_lock (lock); \
(void) (flags); \
} \
while (0)
\end{lstlisting}
\begin{picture}(0,0)
\color{red}
\put(8.5,1.75){\line(-1,0){4.5}}
\put(8.5,1.75){\line(0,-1){2.9}}
\put(8.5,-1.15){\vector(-1,0){1.0}}
\end{picture}
\bigskip
Datei \file{linux-3.7-rc1/kernel/spinlock.h}, ab Zeile 283
\medskip
\begin{lstlisting}
static inline void spin_lock (spinlock_t *lock)
{
raw_spin_lock (&lock->rlock);
}
\end{lstlisting}
\begin{picture}(0,0)
\color{red}
\put(9.3,0.95){\line(-1,0){4.0}}
\put(9.3,0.95){\line(0,-1){2.1}}
\put(9.3,-1.15){\vector(-1,0){1.0}}
\end{picture}
\bigskip
Datei \file{linux-3.7-rc1/kernel/spinlock.h}, Zeile 170
\medskip
\begin{lstlisting}
#define raw_spin_lock(lock) _raw_spin_lock (lock)
\end{lstlisting}
\begin{picture}(0,0)
\color{red}
\put(10.0,0.55){\line(-1,0){0.5}}
\put(10.0,0.55){\line(0,-1){1.7}}
\put(10.0,-1.15){\vector(-1,0){1.3}}
\end{picture}
\bigskip
Datei \file{linux-3.7-rc1/include/linux/spinlock\_api\_smp.h}, Zeile 47
\medskip
\begin{lstlisting}
#define _raw_spin_lock(lock) __raw_spin_lock (lock)
\end{lstlisting}
\begin{picture}(0,0)
\color{red}
\put(10.7,0.55){\line(-1,0){0.5}}
\put(10.7,0.55){\line(0,-1){1.75}} \put(10.7,-1.2){\vector(-1,0){2.3}}
\end{picture}
\bigskip
Datei \file{linux-3.7-rc1/kernel/spinlock.c}, ab Zeile 46 (expandiert):
\medskip
\begin{lstlisting}
void __lockfunc __raw_spin_lock (spinlock_t *lock)
{
for (;;)
{
preempt_disable ();
if (likely (do_raw_spin_trylock (lock)))
break;
preempt_enable ();
if (!(lock)->break_lock)
(lock)->break_lock = 1;
while (!raw_spin_can_lock (lock) && (lock)->break_lock)
arch_spin_relax (&lock->raw_lock);
}
(lock)->break_lock = 0;
}
\end{lstlisting}
\begin{picture}(0,0)
\color{red}
\put(10.7,4.75){\line(-1,0){3.5}}
\put(10.7,4.75){\line(0,-1){5.95}}
\put(10.7,-1.2){\vector(-1,0){1.1}}
\end{picture}
\bigskip
Datei \file{linux-3.7-rc1/include/linux/spinlock.h}, ab Zeile 150:
\medskip
\begin{lstlisting}
static inline int do_raw_spin_trylock (raw_spinlock_t *lock)
{
return arch_spin_trylock (&(lock)->raw_lock);
}
\end{lstlisting}
\begin{picture}(0,0)
\color{red}
\put(11.5,0.95){\line(-1,0){3.5}}
\put(11.5,0.95){\line(0,-1){2.1}}
\put(11.5,-1.15){\vector(-1,0){0.7}}
\end{picture}
\bigskip
Datei \file{arch/x86/include/asm/spinlock.h}, ab Zeile 116:
\medskip
\begin{lstlisting}
static __always_inline int arch_spin_trylock (arch_spinlock_t *lock)
{
return __ticket_spin_trylock (lock);
}
\end{lstlisting}
\begin{picture}(0,0)
\color{red}
\put(9.5,0.95){\line(-1,0){3.5}}
\put(9.5,0.95){\vector(0,-1){1.7}}
\end{picture}
\bigskip
Datei \file{arch/x86/include/asm/spinlock.h}, ab Zeile 65:
\medskip
\begin{lstlisting}
static __always_inline int __ticket_spin_trylock (arch_spinlock_t *lock)
{
arch_spinlock_t old, new;
old.tickets = ACCESS_ONCE (lock->tickets);
if (old.tickets.head != old.tickets.tail)
return 0;
new.head_tail = old.head_tail + (1 << TICKET_SHIFT);
/* cmpxchg is a full barrier, so nothing can move before it */
return cmpxchg (&lock->head_tail, old.head_tail, new.head_tail) == old.head_tail;
}
\end{lstlisting}
\begin{picture}(0,0)
\color{red}
\put(2.2,0.3){\line(0,1){0.4}}
\put(9.0,0.3){\line(-1,0){6.8}}
\put(9.0,0.3){\line(0,-1){1.45}}
\put(9.0,-1.15){\vector(-1,0){3.2}}
\end{picture}
\bigskip
Datei \file{arch/x86/include/asm/cmpxchg.h}, ab Zeile 147:
\medskip
\begin{lstlisting}
#define cmpxchg(ptr, old, new) \
__cmpxchg (ptr, old, new, sizeof (*(ptr)))
\end{lstlisting}
\begin{picture}(0,0)
\color{red}
\put(9.0,0.5){\line(-1,0){1.8}}
\put(9.0,0.5){\line(0,-1){1.65}}
\put(9.0,-1.15){\vector(-1,0){2.2}}
\end{picture}
\bigskip
Datei \file{arch/x86/include/asm/cmpxchg.h}, ab Zeile 131:
\medskip
\begin{lstlisting}
#define __cmpxchg(ptr, old, new, size) \
__raw_cmpxchg ((ptr), (old), (new), (size), LOCK_PREFIX)
\end{lstlisting}
\begin{picture}(0,0)
\color{red}
\put(2.2,-0.1){\line(0,1){0.3}}
\put(9.0,-0.1){\line(-1,0){6.8}}
\put(9.0,-0.1){\line(0,-1){1.05}}
\put(9.0,-1.15){\vector(-1,0){2.2}}
\end{picture}
\bigskip
Datei \file{arch/x86/include/asm/cmpxchg.h}, ab Zeile 110:
\medskip
\begin{lstlisting}
asm volatile (lock "cmpxchgl %2,%1" \
: "=a" (__ret), "+m" (*__ptr) \
: "r" (__new), "0" (__old) \
: "memory");
\end{lstlisting}
\begin{picture}(0,0)
\color{red}
\put(9.8,1.8){\vector(-1,0){0.6}}
\put(9.8,1.2){\line(0,1){0.6}}
\put(9.8,1.1){\makebox(0,0)[t]{\shortstack{atomarer und exklusiver\\Zugriff auf Spinlock\\durch Hardware-Untersttzung}}}
\end{picture}
\end{frame}
\setlength{\pdfpageheight}{\normalpdfpageheight}
%\sectionnonumber{Literaturempfehlung}
%\subsectionnonumber{Automotive Embedded Systeme}
%
%\begin{frame}[c]
%
% \showsectionnonumber
%
% Prof.\ Dr.\ Joachim Wietzke, FH Darmstadt,\\
% Prof.\ Dr.\ Manh Tien Tran, FH Kaiserslautern:
%
% \medskip
%
% \showsubsectionnonumber
%
% \vspace{-\medskipamount}
%
% Springer-Verlag, Berlin, Heidelberg 2005
%
% \bigskip
%
% Lizenz: proprietr
%
% \medskip
%
% (gesetzt mit \textrm{\LaTeX}, ca.\ \EUR{10})
%
%\end{frame}
\begin{frame}
\showsection
\showsubsection
Ressourcen reservieren
\begin{itemize}
\item
\newterm{Semaphor}\\
gemeinsame Variable mehrerer Prozesse\\
zur Regelung des Zugriffs auf eine Ressource\\[\smallskipamount]
Ressource belegt \textarrow\ Kontextwechsel
\medskip
\item
\newterm{Mutex}\\
Mechanismus, damit immer nur ein Proze gleichzeitig\\
auf eine Ressource zugreifen kann
\medskip
\item
\newterm{Spinlock} (\emph{busy waiting\/})\\
leichtgewichtige Alternative zu Kontextwechsel
\medskip
\item
\newterm{Kritischer Abschnitt -- critical section}\\ Programmabschnitt zwischen Reservierung\\
und Freigabe einer Ressource\\
\textarrow\ sollte immer so kurz wie mglich sein
\end{itemize}
\end{frame}
\begin{frame}
\showsection
\showsubsection
\begin{picture}(0,0)
\only<2-3>{\put(6.3,-7){\includegraphics[height=6cm]{philosophenproblem.jpg}}}
\end{picture}%
\newterm{Verklemmungen\/}: Gegenseitiges Blockieren von Ressourcen
\begin{itemize}
\item
\newterm{Deadlock\/}: Proze wartet
\item
\newterm{Livelock\/}: Proze macht andere Dinge\\
(z.\,B.\ \emph{busy waiting\/})
\end{itemize}
\pause
\bigskip
Beispiel: Philosophenproblem
\only<2-3>{%
\begin{itemize}
\item
5 Philosophen, 5 Gabeln
\item
2 Gabeln zum Essen notwendig
\item
Wer essen will, nimmt eine Gabel\\
und wartet notfalls auf die zweite.
\item
Keiner legt eine einzelne Gabel\\
wieder zurck.
\end{itemize}
Jeder hlt 1 Gabel \textarrow\ \newterm{Verklemmung}\\[0.5\smallskipamount]
\pause
\strut\quad schweigen \textarrow\ \newterm{Deadlock}\\
\strut\quad philosophieren weiter \textarrow\ \newterm{Livelock}\\[-1cm]
}
\only<4->{%
\bigskip
Bedingungen fr Verklemmungen:
\begin{minipage}[t]{4.5cm}
\begin{itemize}
\item
Exklusivitt
\item
\newterm{hold and wait}
\item
Entzug nicht mglich
\item
zirkulre Blockade
\end{itemize}
\end{minipage}\pause[5]
\begin{minipage}[t]{7.5cm}
\begin{itemize}
\arrowitem
Spooling
\arrowitem
simultane Zuteilung \arrowitem
Prozesse suspendieren, beenden, \newterm{Rollback}
\arrowitem
Reihenfolge abhngig von Ressourcen
\end{itemize}
\end{minipage}
}
\end{frame}
\subsection{Prioritten}
\begin{frame}
\showsection
\showsubsection
Linux 0.01
\begin{itemize}
\item
Timer-Interrupt: Zhler des aktuellen Prozesses wird dekrementiert;\\
Proze mit hchstem Zhler bekommt Rechenzeit.
\item
Wenn es keinen laufbereiten Proze mit positivem Zhler gibt,\\
bekommen alle Prozesse gem ihrer \newterm{Prioritt\/} neue Zhler zugewiesen.
\item
\emph{keine\/} harte Echtzeit
\arrowitem
\newterm{dynamische Priorittenvergabe\/}:\\
Rechenzeit hngt vom Verhalten des Prozesses ab
\end{itemize}
\medskip
Echtzeitbetriebssysteme
\begin{itemize}
\item
Prozesse knnen einen festen Anteil an Rechenzeit bekommen.
\item
Bei Ereignissen knnen Prozesse hoher Prioritt\\
Prozesse niedriger Prioritt unterbrechen, aber nicht umgekehrt.
\arrowitem
\newterm{statische Priorittenvergabe}
\end{itemize}
\end{frame}
\begin{frame}
\showsection
\showsubsection
Echtzeitbetriebssysteme
\begin{itemize}
\item
Prozesse knnen einen festen Anteil an Rechenzeit bekommen.
\item
Bei Ereignissen knnen Prozesse hoher Prioritt\\
Prozesse niedriger Prioritt unterbrechen, aber nicht umgekehrt.
\end{itemize}
\vspace{0cm plus 1filll}
\begin{center}
\begin{picture}(11,4)(-1,0)
\small
\put(-0.1,0.5){\vector(1,0){10.1}}
\put(9.75,0.4){\makebox(0,0)[tr]{Zeit}}
\put(0,0.4){\vector(0,1){3.6}} \put(-0.1,3.75){\makebox(0,0)[tr]{Prioritt}}
\put(1,3){{\color{lightorange}\rule{0.5cm}{0.4cm}}}
\put(3,3){{\color{lightorange}\rule{0.7cm}{0.4cm}}}
\put(5,3){{\color{lightorange}\rule{0.6cm}{0.4cm}}}
\put(7,3){{\color{lightorange}\rule{0.5cm}{0.4cm}}}
\put(9,3){{\color{lightorange}\rule{0.7cm}{0.4cm}}}
\put(0,3){\line(1,0){10}}
\put(0,1){{\color{lightgreen}\rule{1cm}{0.4cm}}}
\put(1.5,1){{\color{lightgreen}\rule{1.5cm}{0.4cm}}}
\put(3.7,1){{\color{lightgreen}\rule{0.6cm}{0.4cm}}}
\alt<1>{%
\put(7.9,1){{\color{lightgreen}\rule{1.1cm}{0.4cm}}}
}{%
\put(8.1,1){{\color{lightgreen}\rule{0.9cm}{0.4cm}}}
}
\put(9.7,1){{\color{lightgreen}\rule{0.3cm}{0.4cm}}}
\put(0,1){\line(1,0){10}}
\pause
\put(4.6,2){{\color{lightyellow}\rule{0.4cm}{0.4cm}}}
\put(5.7,2){{\color{lightyellow}\rule{1.3cm}{0.4cm}}}
\put(7.7,2){{\color{lightyellow}\rule{0.4cm}{0.4cm}}}
\put(0,2){\line(1,0){10}}
\end{picture}
\end{center}
\end{frame}
\subsectionnonumber{Prioritten \protect\color{darkgray}und Ressourcen}
\begin{frame}
\showsection
\showsubsection
\only<4->{%
Der hher priorisierte Proze bewirkt selbst,\\
da er eine Ressource versptet bekommt.
\medskip
\textarrow\ \newterm{begrenzte Priorittsinversion}
\medskip
maximale Verzgerung: Lnge des kritischen Bereichs
}
\vspace{0cm plus 1filll}
\begin{center}
\begin{picture}(11,4)(-1,0)
\small
\put(-0.1,0.5){\vector(1,0){10.1}}
\put(9.75,0.4){\makebox(0,0)[tr]{Zeit}}
\put(0,0.4){\vector(0,1){3.6}}
\put(-0.1,3.75){\makebox(0,0)[tr]{Prioritt}}
\put(1,3){{\color{lightorange}\rule{0.5cm}{0.4cm}}}
\only<1-2>{\put(3,3){{\color{lightorange}\rule{0.7cm}{0.4cm}}}}
\only<3->{\put(3,3){{\color{lightorange}\rule{0.4cm}{0.4cm}}}}
\only<3-4>{%
\put(3.4,3){{\color{red}\rule{0.8cm}{0.4cm}}}
\put(4.2,3){{\color{lightorange}\rule{0.2cm}{0.4cm}}}
{\thicklines \put(3.3,2.95){\line(2,1){1.0}}
\put(3.3,3.45){\line(2,-1){1.0}}}
}
\only<5->{%
\put(3.9,3){{\color{red}\rule{0.8cm}{0.4cm}}}
\put(4.7,3){{\color{lightorange}\rule{0.2cm}{0.4cm}}}
}
\put(5,3){{\color{lightorange}\rule{0.6cm}{0.4cm}}}
\only<1-2>{%
\put(5.4,3){{\color{red}\rule{0.8cm}{0.4cm}}}
\put(6.2,3){{\color{lightorange}\rule{0.2cm}{0.4cm}}}
}
\put(7,3){{\color{lightorange}\rule{0.5cm}{0.4cm}}}
\put(9,3){{\color{lightorange}\rule{0.7cm}{0.4cm}}}
\put(0,3){\line(1,0){10}}
\only<2->{%
\put(0,1){{\color{lightgreen}\rule{1cm}{0.4cm}}}
\put(1.5,1){{\color{lightgreen}\rule{1.5cm}{0.4cm}}}
\put(2.6,1){{\color{medgreen}\rule{0.4cm}{0.4cm}}}
\only<2-4>{%
\put(3.7,1){{\color{medgreen}\rule{0.5cm}{0.4cm}}}
\put(4.2,1){{\color{lightgreen}\rule{0.3cm}{0.4cm}}}
}
\only<5->{%
\put(3.4,1){{\color{medgreen}\rule{0.5cm}{0.4cm}}}
\put(4.9,1){{\color{lightgreen}\rule{0.1cm}{0.4cm}}}
\put(5.6,1){{\color{lightgreen}\rule{0.2cm}{0.4cm}}}
}
\put(7.7,1){{\color{lightgreen}\rule{1.3cm}{0.4cm}}}
\put(9.7,1){{\color{lightgreen}\rule{0.3cm}{0.4cm}}}
\put(0,1){\line(1,0){10}}
}
\end{picture}
\end{center}
\end{frame}
\begin{frame}
\showsection
\showsubsection
\visible<4->{%
Ein Proze mit mittlerer Prioritt bewirkt,
da ein Proze mit hoher Prioritt eine Ressource berhaupt nicht bekommt.
\medskip
\textarrow\ }\newterm{unbegrenzte Priorittsinversion}
\pause
\vspace{0cm plus 1filll}
\begin{center}
\begin{picture}(11,4)(-1,0)
\small
\put(-0.1,0.5){\vector(1,0){10.1}}
\put(9.75,0.4){\makebox(0,0)[tr]{Zeit}}
\put(0,0.4){\vector(0,1){3.6}}
\put(-0.1,3.75){\makebox(0,0)[tr]{Prioritt}}
\put(1,3){{\color{lightorange}\rule{0.5cm}{0.4cm}}}
\put(3,3){{\color{lightorange}\rule{0.4cm}{0.4cm}}}
\only<2>{%
\put(3.4,3){{\color{red}\rule{0.8cm}{0.4cm}}}
\put(4.2,3){{\color{lightorange}\rule{0.2cm}{0.4cm}}}
{\thicklines
\put(3.3,2.95){\line(2,1){1.0}} \put(3.3,3.45){\line(2,-1){1.0}}}
\put(5,3){{\color{lightorange}\rule{0.6cm}{0.4cm}}}
\put(7,3){{\color{lightorange}\rule{0.5cm}{0.4cm}}}
\put(9,3){{\color{lightorange}\rule{0.7cm}{0.4cm}}}
}
\put(0,3){\line(1,0){10}}
\only<2->{%
\put(0,1){{\color{lightgreen}\rule{1cm}{0.4cm}}}
\put(1.5,1){{\color{lightgreen}\rule{1.1cm}{0.4cm}}}
\alt<1-4>{%
\put(2.6,1){{\color{medgreen}\rule{0.4cm}{0.4cm}}}
}{%
\put(2.6,1){{\color{medgreen}\rule{0.2cm}{0.4cm}}}
}
\only<2>{%
\put(3.7,1){{\color{medgreen}\rule{0.5cm}{0.4cm}}}
\put(4.2,1){{\color{lightgreen}\rule{0.3cm}{0.4cm}}}
}
\only<3-4>{%
\put(3.4,1){{\color{medgreen}\rule{0.5cm}{0.4cm}}}
% \put(3.9,1){{\color{lightgreen}\rule{0.3cm}{0.4cm}}}
}
\only<2>{%
\put(7.7,1){{\color{lightgreen}\rule{1.3cm}{0.4cm}}}
\put(9.7,1){{\color{lightgreen}\rule{0.3cm}{0.4cm}}}
}
\put(0,1){\line(1,0){10}}
}
\only<5->{%
\put(2.8,2){{\color{lightyellow}\rule{0.2cm}{0.4cm}}}
\put(3.4,2){{\color{lightyellow}\rule{6.6cm}{0.4cm}}}
\put(0,2){\line(1,0){10}}
}
\end{picture}
\end{center}
\end{frame}
\begin{frame}
\showsection
\showsubsection
Ein Proze mit mittlerer Prioritt bewirkt,
da ein Proze mit hoher Prioritt eine Ressource berhaupt nicht bekommt.
\medskip
\textarrow\ \newterm{unbegrenzte Priorittsinversion}
\medskip
Beispiel: Beinahe-Verlust der Marssonde \emph{Pathfinder\/} im Juli 1997
\only<1>{%
\begin{center}
\includegraphics[width=8.7cm]{pathfinder.jpg}
\end{center}
\vspace*{-1cm}
}
\only<2->{%
\bigskip
Gegenmanahmen
\begin{itemize}
\item
\newterm{Priority Inheritance -- Priorittsvererbung}\\ Der Besitzer des Mutex erbt die Prioritt\\
des Prozesses, der auf den Mutex wartet.
\smallskip
\item
\newterm{Priority Ceiling -- Priorittsobergrenze}\\
Der Besitzer des Mutex bekommt sofort\\
die Prioritt des hchstmglichen Prozesses,\\
der evtl.\ den Mutex bentigen knnte.
\smallskip
\item
\newterm{Priority Aging}\\
Die Prioritt wchst mit der Wartezeit.
\pause[3]
\begin{picture}(0,0)
\put(1.2,2.5){\makebox(0,0)[l]{$\left\}\rule{0pt}{1.7cm}\right.$
\begin{minipage}{4cm}
nur mglich, wenn\\
Mutexe im Spiel sind
\end{minipage}}}
\end{picture}
\end{itemize}
\vspace*{-1cm}
}
\end{frame}
\end{document}