svn commit: r256433 - in user/glebius/course: . 03.processes&threads 04.synchronisation
Gleb Smirnoff
glebius at FreeBSD.org
Sun Oct 13 21:46:10 UTC 2013
Author: glebius
Date: Sun Oct 13 21:46:08 2013
New Revision: 256433
URL: http://svnweb.freebsd.org/changeset/base/256433
Log:
Not yet cooked up slides on threads & processes and on synchronisation.
Added:
user/glebius/course/03.processes&threads/
user/glebius/course/03.processes&threads/Makefile (contents, props changed)
user/glebius/course/03.processes&threads/lection.tex
user/glebius/course/04.synchronisation/
user/glebius/course/04.synchronisation/Makefile (contents, props changed)
user/glebius/course/04.synchronisation/lection.tex
Modified:
user/glebius/course/course.tex
Added: user/glebius/course/03.processes&threads/Makefile
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ user/glebius/course/03.processes&threads/Makefile Sun Oct 13 21:46:08 2013 (r256433)
@@ -0,0 +1,13 @@
+NAME?= lection
+
+TMP= $(NAME).aux $(NAME).log $(NAME).nav $(NAME).out $(NAME).snm \
+ $(NAME).toc $(NAME).vrb
+
+.MAIN: $(NAME).pdf
+
+.SUFFIXES: .pdf .tex
+.tex.pdf:
+ pdflatex -file-line-error -halt-on-error ${.IMPSRC}
+
+clean:
+ rm -f -- $(TMP) texput.log
Added: user/glebius/course/03.processes&threads/lection.tex
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ user/glebius/course/03.processes&threads/lection.tex Sun Oct 13 21:46:08 2013 (r256433)
@@ -0,0 +1,246 @@
+\documentclass{beamer}
+
+\usepackage[utf8]{inputenc}
+\usepackage[russian]{babel}
+\usepackage{tikz}
+\usepackage{url}
+\usepackage{xcolor}
+\usepackage{listings}
+\usepackage{verbatim}
+\usepackage{ifthen}
+
+\usetikzlibrary{positioning}
+\usetikzlibrary{shapes}
+\usetikzlibrary{calc}
+
+\input{../course.tex}
+
+\title{Processes and threads}
+
+\begin{document}
+
+\begin{frame}
+\titlepage
+\end{frame}
+
+\FootReferences{}{sys/sys/proc.h}
+\begin{frame}
+\frametitle{Process structure}
+\note {
+ - A process is a virtual machine that kernel creates for
+ an application. It provides VM and CPU resources.\\
+ - The slide is a minimal layout of a UNIX process. Actual
+ size of struct proc is > 1Kb.
+}
+\begin{tikzpicture}[every node/.style={draw, node distance=10mm}]
+ \node [name=proc, struct, inner sep=2mm, rectangle split parts = 8] {
+ \textbf{struct proc}
+ \nodepart{two} struct vmspace *p\_vmspace
+ \nodepart{three} struct sysentvec *p\_sysent
+ \nodepart{four} struct filedesc *p\_fd
+ \nodepart{five} struct ucred *p\_ucred
+ \nodepart{six} struct plimit *p\_limit
+ \nodepart{seven} \ldots
+ \nodepart{eight} TAILQ\_HEAD() p\_threads
+ };
+
+ \node[name=vm, right=of proc.two east, rounded corners]
+ { VM space };
+ \draw [->] (proc.two east) -- (vm);
+ \node[name=sysent, right=of proc.three east, rounded corners]
+ { syscall vector };
+ \draw [->] (proc.three east) -- (sysent);
+ \node[name=fdesc, right=of proc.four east, rounded corners]
+ { file descriptor table };
+ \draw [->] (proc.four east) -- (fdesc);
+ \node[name=rlim, right=of proc.five east, rounded corners]
+ { resource limits };
+ \draw [->] (proc.five east) -- (rlim);
+ \node[name=cred, right=of proc.six east, rounded corners]
+ { credentials };
+ \draw [->] (proc.six east) -- (cred);
+
+ % threads
+ \node [name=thread1, struct, rectangle split parts = 1,
+ node distance=5mm, below right=of proc]
+ { \textbf{struct thread} };
+ \node [name=thread2, struct, rectangle split parts = 1,
+ node distance=5mm, right=of thread1]
+ { \textbf{struct thread} };
+ \draw [->] (proc.eight east) to [out=0, in=180] (thread1.west);
+ \draw [->] (thread1) -- (thread2);
+\end{tikzpicture}
+\end{frame}
+
+
+\begin{frame}
+\frametitle{p\_state - the process state}
+\begin{itemize}
+ \item{PRS\_NEW}
+ \item{PRS\_NORMAL}
+ \item{PRS\_ZOMBIE}
+\end{itemize}
+\end{frame}
+
+
+\begin{frame}
+\frametitle{Thread structure}
+\note {
+ - Thread is a executing entity within a process. It includes all
+ the data that can't be shared.\\
+ - A minimal struct thread layout. Actual size > 1 Kb.
+}
+\begin{tikzpicture}[every node/.style={draw, node distance=10mm}]
+ \node [name=thread, struct, inner sep=2mm, rectangle split parts = 6] {
+ \textbf{struct thread}
+ \nodepart{two} struct proc *td\_proc
+ \nodepart{three} struct proc *td\_sched
+ \nodepart{four} struct pcb *td\_pcb
+ \nodepart{five} struct vm\_object *td\_kstack\_obj
+ \nodepart{six} \ldots
+ };
+
+ \node [name=proc, right=of thread.two east, struct, rectangle split parts = 1]
+ { \textbf{struct proc} };
+ \draw [->] (thread.two east) -- (proc);
+ \node [name=sched, right=of thread.three east, rounded corners]
+ { scheduling info };
+ \draw [->] (thread.three east) -- (sched);
+ \node [name=pcb, right=of thread.four east, rounded corners]
+ { thread control block (MD) };
+ \draw [->] (thread.four east) -- (pcb);
+ \node [name=kstack, right=of thread.five east, rounded corners]
+ { kernel stack };
+ \draw [->] (thread.five east) -- (kstack);
+\end{tikzpicture}
+\end{frame}
+
+
+\FootReferences{}{sys/sys/proc.h, sys/kern/kern\_thread.c,
+ sys/kern/sched\_ule.c}
+\begin{frame}
+\frametitle{td\_state - the thread state}
+\begin{itemize}
+ \item{TDS\_INACTIVE}
+ \item{TDS\_CAN\_RUN}
+ \item{TDS\_RUNQ}
+ \item{TDS\_RUNNING}
+ \item{
+ TDS\_INHIBITED\\
+ \onslide<2> {
+ Combination of inhibitors in td\_inhibitors:
+ \begin{itemize}
+ \item{TDI\_SUSPENDED}
+ \item{TDI\_SLEEPING}
+ \item{TDI\_SWAPPED}
+ \item{TDI\_LOCK}
+ \item{TDI\_IWAIT}
+ \end{itemize}
+ }
+ }
+\end{itemize}
+\end{frame}
+
+
+\FootReferences{}{}
+\begin{frame}
+\frametitle{Historic note: M:N vs 1:1}
+\begin{columns}[c]
+ \begin{column}{.46\paperwidth}
+ \begin{figure}\begin{tikzpicture}
+ \node [name=thread, struct, rectangle split parts = 1]
+ { \textbf{struct thread} };
+ \draw ($(thread) + (-.33\paperwidth, 2cm)$) --
+ node[very near end, above] { process }
+ node[very near end, below] { kernel }
+ ($(thread) + (.13\paperwidth, 2cm)$);
+ \node [name=uthr1, draw, ellipse, fill=white,
+ node distance=0, anchor=center,
+ above left=.3\paperheight and -.08\paperwidth of thread.center,
+ text width=2cm, align=center]
+ { user space scheduling entity };
+ \draw [->] (uthr1) -- (thread);
+ \node [name=uthr2, draw, ellipse, fill=white,
+ node distance=0, anchor=center,
+ above left=.25\paperheight and .1\paperwidth of thread.center,
+ text width=2cm, align=center]
+ { user space scheduling entity };
+ \node [name=thread2, struct, rectangle split parts = 1,
+ node distance=0, above left=3mm and -10mm of thread]
+ { \textbf{struct thread} };
+ \draw [->] (uthr2) -- (thread2);
+
+ \node [name=pthread1, node distance=.6\paperheight, above=of thread]
+ { pthread\_t };
+ \node [name=pthread2, node distance=0, left=.1\paperwidth of pthread1]
+ { pthread\_t };
+ \node [name=pthread21, node distance=0, below right=of pthread2]
+ { pthread\_t };
+ \node [name=pthread22, node distance=0, below right=of pthread21]
+ { pthread\_t };
+ \node [name=pthread23, node distance=0, below left=of pthread21]
+ { pthread\_t };
+
+ \draw [->] (pthread23) -- (uthr2);
+ \draw [->] (pthread22) -- (uthr1);
+ \draw [->] (pthread21) -- (uthr1);
+ \draw [->] (pthread1) to [out=270,in=100]
+ (node cs:name=uthr1,angle=100);
+ \draw [->] (pthread2.south) to [out=350,in=80]
+ (node cs:name=uthr2,angle=80);
+ \end{tikzpicture}\end{figure}
+ \end{column}
+ \begin{column}{.08\paperwidth}
+ \LARGE{VS}
+ \end{column}
+ \begin{column}{.46\paperwidth}
+ \begin{figure}\begin{tikzpicture}
+ \node [name=thread, struct, rectangle split parts = 1]
+ { \textbf{struct thread} };
+ \draw ($(thread) + (-.23\paperwidth, 2cm)$) --
+ node[very near end, above] { process }
+ node[very near end, below] { kernel }
+ ($(thread) + (.23\paperwidth, 2cm)$);
+ \node [name=pthread, node distance=.6\paperheight, above=of thread]
+ { pthread\_t };
+ \draw [->] (pthread) -- (thread);
+ \end{tikzpicture}\end{figure}
+ \end{column}
+\end{columns}
+\end{frame}
+
+
+\begin{frame}
+\frametitle{Historic note: M:N vs 1:1}
+\only<1> {
+ \begin{itemize}
+ \item{1993 Solaris 2.2 introduces multithreading via non-standard API}
+ \item{1995 Solaris 2.5 supports POSIX threads API, \textbf{M:N model}}
+ \item{2000 FreeBSD starts SMPng project targeted at \textbf{M:N}}
+ \item{2000 Solaris 8 provides \textbf{1:1} threading as option}
+ \item{2001 Linux starts multithreading project targeted at \textbf{1:1}
+ with \textbf{M:N} as experimental option}
+ \item{2001 Mac OS X released with \textbf{1:1} threading}
+ \item{2002 Solaris 9 uses \textbf{1:1} threading as default}
+ \item{2003 Linux abandons experimental \textbf{M:N} project}
+ \item{2004 FreeBSD 5.3 released with Kernel Scheduling Entities
+ (\textbf{M:N}) threading as default, \textbf{1:1} optional}
+ \item{2004 NetBSD 2.0 released with Scheduler Activations (\textbf{M:N})}
+ \item{2004 Linux 2.6 released with \textbf{1:1} threading}
+ \end{itemize}
+}
+\only<2-> {
+ \begin{itemize}
+ \item{2005 FreeBSD moves focus to \textbf{1:1}}
+ \item{2007 NetBSD abandons SA (\textbf{M:N})}
+ \item{2008 FreeBSD abandons KSE (\textbf{M:N})}
+ \item{2008 FreeBSD 7.0 released with \textbf(1:1) as default,
+ \textbf{M:N} optional}
+ \item{2009 NetBSD 5.0 released with \textbf{1:1} as only option}
+ \item{2009 FreeBSD 8.0 released with \textbf{1:1} as only option}
+ \onslide<3>\item{2009 Windows 7 introduces User-Mode Scheduling}
+ \end{itemize}
+}
+\end{frame}
+
+\end{document}
Added: user/glebius/course/04.synchronisation/Makefile
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ user/glebius/course/04.synchronisation/Makefile Sun Oct 13 21:46:08 2013 (r256433)
@@ -0,0 +1,13 @@
+NAME?= lection
+
+TMP= $(NAME).aux $(NAME).log $(NAME).nav $(NAME).out $(NAME).snm \
+ $(NAME).toc $(NAME).vrb
+
+.MAIN: $(NAME).pdf
+
+.SUFFIXES: .pdf .tex
+.tex.pdf:
+ pdflatex -file-line-error -halt-on-error ${.IMPSRC}
+
+clean:
+ rm -f -- $(TMP) texput.log
Added: user/glebius/course/04.synchronisation/lection.tex
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ user/glebius/course/04.synchronisation/lection.tex Sun Oct 13 21:46:08 2013 (r256433)
@@ -0,0 +1,222 @@
+\documentclass{beamer}
+
+\usepackage[utf8]{inputenc}
+\usepackage[russian]{babel}
+\usepackage{tikz}
+\usepackage{url}
+\usepackage{xcolor}
+\usepackage{listings}
+\usepackage{verbatim}
+\usepackage{ifthen}
+\usepackage{bytefield}
+
+\usetikzlibrary{positioning}
+\usetikzlibrary{shapes}
+\usetikzlibrary{calc}
+
+\input{../course.tex}
+
+\title{Synchronisation in FreeBSD kernel}
+
+\begin{document}
+
+\begin{frame}
+\titlepage
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Data consistency problem}
+\begin{beamercolorbox}[rounded=true,shadow=true]{source}
+\lstset{language=C}
+\begin{lstlisting}
+elm1->elm_next = elm2;
+elm2->elm_next = elm3;
+elm3->elm_prev = elm2;
+elm2->elm_prev = elm1;
+\end{lstlisting}
+\end{beamercolorbox}
+\begin{figure}
+\begin{tikzpicture}[every node/.style={draw, node distance=20mm}]
+ \node [name=elm1, struct, rectangle split parts = 3] {
+ \textbf{elm1}
+ \nodepart{two} *elm\_prev
+ \nodepart{three} *elm\_next
+ };
+ \node [name=elm2, below right=of elm1, struct, rectangle split parts = 3] {
+ \textbf{elm2}
+ \nodepart{two} *elm\_prev
+ \nodepart{three} *elm\_next
+ };
+ \node [name=elm3, above right=of elm2, struct, rectangle split parts = 3] {
+ \textbf{elm3}
+ \nodepart{two} *elm\_prev
+ \nodepart{three} *elm\_next
+ };
+ \onslide<1> {
+ \draw [->] (elm1.three east) to [out=0,in=180] (elm3.one west);
+ }
+ \onslide<-3> {
+ \draw [->] (elm3.two west) to [out=180,in=0] (elm1.one east);
+ }
+ \onslide<2-> {
+ \draw [->] (elm1.three east) to [out=0,in=180] (elm2.one west);
+ }
+ \onslide<3-> {
+ \draw [->] (elm2.three east) to [out=0,in=180] (elm3.one west);
+ }
+ \onslide<4-> {
+ \draw [->] (elm3.two west) to [out=180,in=0] (elm2.one east);
+ }
+ \onslide<5-> {
+ \draw [->] (elm2.two west) to [out=180,in=0] (elm1.one east);
+ }
+\end{tikzpicture}
+\end{figure}
+\end{frame}
+
+
+\FootReferences{critical(9)}{sys/kern/kern\_switch.c}
+\begin{frame}[fragile]
+\frametitle{Critical section}
+{\Large{Solution for uniprocessor: enter \emph{critical section}, marking current thread as non-preemptable.}}
+\begin{beamercolorbox}[rounded=true,shadow=true]{source}
+\lstset{language=C}
+\begin{lstlisting}
+critical_enter();
+elm1->elm_next = elm2;
+elm2->elm_next = elm3;
+elm3->elm_prev = elm2;
+elm2->elm_prev = elm1;
+critical_exit();
+\end{lstlisting}
+\end{beamercolorbox}
+\end{frame}
+
+
+\begin{frame}[fragile]
+\frametitle{Critical section (implementation)}
+\emph{Hard} critical sections disable interrupts.
+\emph{Soft} ones advice mark thread as non-preemptable.
+\Man{critical}{9} is \emph{soft}.
+\begin{beamercolorbox}[rounded=true,shadow=true]{source}
+\lstset{language=C}
+\begin{lstlisting}
+void
+critical_enter(void)
+{
+ struct thread *td;
+
+ td = curthread;
+ td->td_critnest++;
+}
+\end{lstlisting}
+\end{beamercolorbox}
+\end{frame}
+
+
+\begin{frame}
+\frametitle{Maintaining data consistency on SMP}
+\begin{tabular}{cc}
+ {\Large CPU 1, thread A} & {\Large CPU 2, thread B}\\
+\only<1> { & \\ }
+\only<2> { tdA->td\_critnest++ & tdB->td\_critnest++ \\ }
+\only<1-2> {
+ elm1->elm\_next = elm2; & elm1->elm\_next = elm2;\\
+ elm2->elm\_next = elm3; & elm2->elm\_next = elm3;\\
+ elm3->elm\_prev = elm2; & elm3->elm\_prev = elm2;\\
+ elm2->elm\_prev = elm1; & elm2->elm\_prev = elm1;\\
+}
+\only<3> {
+ lock(elm\_lock); & lock(elm\_lock);\\
+ elm1->elm\_next = elm2; & \emph{blocked}\\
+ elm2->elm\_next = elm3; & \emph{blocked}\\
+ elm3->elm\_prev = elm2; & \emph{blocked}\\
+ elm2->elm\_prev = elm1; & \emph{blocked}\\
+ unlock(elm\_lock); & elm1->elm\_next = elm2;\\
+ \ldots & elm2->elm\_next = elm3;\\
+}
+\end{tabular}
+\end{frame}
+
+
+\FootReferences{mutex(9)}{}
+\begin{frame}[fragile]
+\frametitle{Naive idea of mutual exclusion lock (mutex)}
+\begin{beamercolorbox}[rounded=true,shadow=true]{source}
+\lstset{language=C}
+\begin{lstlisting}
+void
+lock(lock_t l)
+{
+ struct thread *td;
+
+ td = curthread;
+
+spin:
+ if (l == NULL)
+ l = (lock_t )td;
+ else
+ goto spin;
+}
+\end{lstlisting}
+\end{beamercolorbox}
+\end{frame}
+
+
+\FootReferences{atomic(9)}{sys/amd64/include/atomic.h}
+\begin{frame}[fragile]
+\frametitle{Working idea of a minimal mutual exclusion lock (mutex)}
+\begin{beamercolorbox}[rounded=true,shadow=true]{source}
+\lstset{language=C}
+\begin{lstlisting}
+void
+lock(lock_t l)
+{
+ struct thread *td;
+
+ td = curthread;
+
+spin:
+ if (atomic_cmpset(&l, NULL, td) == 0)
+ goto spin;
+}
+\end{lstlisting}
+\end{beamercolorbox}
+\end{frame}
+
+
+\FootReferences{mutex(9), atomic(9)}{sys/kern/mutex.h}
+\begin{frame}[fragile]
+\frametitle{mutex(9) implementation}
+\begin{verbatim}
+struct mtx {
+ /* Common lock properties. */
+ struct lock_object lock_object;
+ /* Owner and flags. */
+ volatile uintptr_t mtx_lock;
+};
+\end{verbatim}
+mtx\_lock:\\
+\begin{bytefield}{32}
+\bitheader[endianness=big]{0,1,2,3,10,11} \\
+\bitbox{21}{thread pointer} & \bitbox{8}{unused} &
+\bitbox{1}{U} & \bitbox{1}{C} & \bitbox{1}{R}
+\end{bytefield}
+\begin{verbatim}
+#define MTX_RECURSED 0x00000001 /* lock recursed */
+#define MTX_CONTESTED 0x00000002 /* lock contested */
+#define MTX_UNOWNED 0x00000004 /* free mutex */
+
+atomic_cmpset_acq_ptr(&(mp)->mtx_lock, MTX_UNOWNED, (tid))
+\end{verbatim}
+\end{frame}
+
+
+\FootReferences{mutex(9)}{sys/kern/mutex.h, sys/kern/kern_mutex.c}
+\begin{frame}
+\frametitle{mutex(9) implementation}
+
+\end{frame}
+
+
+\end{document}
Modified: user/glebius/course/course.tex
==============================================================================
--- user/glebius/course/course.tex Sun Oct 13 19:25:23 2013 (r256432)
+++ user/glebius/course/course.tex Sun Oct 13 21:46:08 2013 (r256433)
@@ -6,9 +6,14 @@
\definecolor{Dgrey}{HTML}{DDDDDD}
\definecolor{Egrey}{HTML}{EEEEEE}
+\definecolor{struct}{HTML}{999999}
+
% trace
\setbeamercolor{trace}{fg=black,bg=Cgrey}
+% source
+\setbeamercolor{source}{fg=black,bg=Cgrey}
+
% terminal
\setbeamercolor{terminal}{fg=white,bg=black}
@@ -19,9 +24,9 @@
\newcommand{\Man}[2]{
\colorbox{white}{\color{man}#1(#2)}
}
-\setbeamercolor{manlabel}{fg=black,bg=man}
+\setbeamercolor{manref}{fg=black,bg=man}
\newcommand{\manlabel}[1]{
- \begin{beamercolorbox}[rounded=true,shadow=true,sep=0pt,colsep=0pt]{manlabel}
+ \begin{beamercolorbox}[rounded=true,shadow=true,sep=0pt,colsep=0pt]{manref}
\small{#1}
\end{beamercolorbox}
}
@@ -40,3 +45,40 @@
\small{#1}
\end{beamercolorbox}
}
+
+\tikzset { struct/.style = {
+ draw, thick,
+ rectangle split,
+ rectangle split part fill={struct!50, white!50},
+} }
+
+%
+% Footnotes for source/manual references.
+%
+\newcommand\ManRefSw{}
+\newcommand\SrcRefSw{}
+\makeatletter
+\newcommand*\FootReferences[2]{
+ \renewcommand\ManRefSw{#1}
+ \renewcommand\SrcRefSw{#2}
+ \beamer at calculateheadfoot
+}
+\makeatother
+\setbeamertemplate{footline}{%
+\ifthenelse{\NOT \equal{\ManRefSw}{}} {
+ \begin{beamercolorbox}
+ [wd=\paperwidth,ht=2.25ex,dp=1ex,left]{manref}%
+ \hspace*{1em}Manual page(s): \ManRefSw
+ \end{beamercolorbox}
+ }
+ % else
+ {}
+\ifthenelse{\NOT \equal{\SrcRefSw}{}} {
+ \begin{beamercolorbox}
+ [wd=\paperwidth,ht=2.25ex,dp=1ex,left]{srcref}%
+ \hspace*{1em}Source code reference: \SrcRefSw
+ \end{beamercolorbox}
+ }
+ % else
+ {}
+}
More information about the svn-src-user
mailing list