Date: Sun, 13 Oct 2013 21:46:09 +0000 (UTC) From: Gleb Smirnoff <glebius@FreeBSD.org> To: src-committers@freebsd.org, svn-src-user@freebsd.org Subject: svn commit: r256433 - in user/glebius/course: . 03.processes&threads 04.synchronisation Message-ID: <201310132146.r9DLk9UF025453@svn.freebsd.org>
next in thread | raw e-mail | index | archive | help
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@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 + {} +}
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201310132146.r9DLk9UF025453>