\documentclass[colorlinks]{beamer}

\usepackage[T1]{fontenc}
\usepackage[utf8x]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{default}

\usepackage{amssymb}

\usepackage{hyperref}

\usepackage{fancyvrb}

\usetheme{Warsaw}

\begin{document}

\def\oneitem#1{\begin{itemize}\item #1\end{itemize}}

\title{Многопоточное программирование и Java}
\subtitle{Корректность, методики, оптимизация}
\author{Евгений Кирпичев\\~Яндекс}

\date{\today}

\setcounter{tocdepth}{2}
\AtBeginSection[]
{
   \begin{frame}
       \frametitle{Содержание}
       \tableofcontents[currentsection]
   \end{frame}
}

\def\link#1{\small{\url{#1}}}

\begin{frame}[plain]
 \titlepage
\end{frame}

\begin{frame}
 \frametitle{Цель доклада}
 Расширить кругозор в области многопоточного программирования вообще и на Java в частности.
 \begin{itemize}
  \item Корректность
  \begin{itemize}
    \item Как сформулировать, проверить, повысить, гарантировать
  \end{itemize}
  \item Методики и велосипеды
  \begin{itemize}
    \item Мудрость предков
  \end{itemize}
  \item Производительность
  \begin{itemize}
    \item Что влияет на производительность и как повлиять самому
  \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Проблемы многопоточного программирования}
 Писать многопоточные программы - трудно.
 \begin{itemize}
  \item Обычно слабая поддержка со стороны (особенно императивного) языка
  \item Трудно сделать корректными
  \item Адски трудно тестировать
  \item Трудно сделать быстрыми (не всё хорошо масштабируется)
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Классификация многопоточных программ}
 \begin{block}{Parallelism vs Concurrency}
   \begin{description}
    \item[Parallel] Одна задача бьется на много частей
    \item[Concurrent] Много разных задач
   \end{description}
 \end{block}
\end{frame}

\begin{frame}
 \frametitle{Классификация многопоточных программ (contd.)}
 Программы бывают разные.
 \begin{tabular}{c|ccc}
   & Raytracer & Server & IDE \\
  \hline 
  Сколько задач? & Много & Много & Мало \\
  Зависимы? & Нет & Нет & Да \\
  Общие ресурсы? & Нет & Да & Да \\
  Трудность & CPU perf & IO perf & Корректность
 \end{tabular}
\end{frame}

\section{Корректность}
\subsection{Причины багов}

\begin{frame}
 \frametitle{Причины багов}
 Корень \alert{всех} зол - изменяемое состояние.
 \begin{itemize}
  \item $N$ нитей, $K$ состояний $\Rightarrow$ $O(K^N)$ переплетений
  \item Промежуточные состояния \emph{видимы}
  \item Даже метод - это больше не черный ящик
  \oneitem{Его тело больше не атомарно}
  \item Корректные многопоточные программы не модульны
  \oneitem{Sequentialy correct + Sequentially correct $\neq$ Concurrently correct}
 \end{itemize}
\end{frame}

\subsection{Доказательство корректности}

\begin{frame}
 \frametitle{Доказуемая корректность}
 Face it:
 \begin{itemize}
  \item Либо программа \emph{доказуемо} корректна
  \item Либо она, почти наверняка, некорректна
  \begin{itemize}
    \item Полностью оттестировать невозможно
    \item Вероятность бага $10^{-8}$, $10^9$ вызовов за неделю - и вероятность уже $1-e^{-10} \approx 1$
  \end{itemize}
  \item Работает \emph{на бумаге} или не работает вообще
 \end{itemize}
\end{frame}


\begin{frame}
 \frametitle{Доказуемая корректность}
 Формальные методы рассуждения и доказательства корректности \emph{необходимы}.

 Это не роскошь для фриков.
\end{frame}

\subsubsection{Структуры Крипке и LTL}
\begin{frame}
 \frametitle{Структура Крипке}
 Структура Крипке $\approx$ граф состояний.
 \begin{itemize}
  \item Множество состояний
  \item Некоторые \emph{начальные}
  \item Некоторые соединены \emph{переходом}
  \oneitem{Переход \emph{безусловный}}
  \item Множество \emph{названий фактов}
  \item В каждом состоянии верны некоторые факты.
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Структура Крипке}
 Микроволновка.
 \begin{center}
  \includegraphics[scale=0.5]{microwave.pdf}
 \end{center}
\end{frame}

\begin{frame}
 \frametitle{Структура Крипке}
 Переходы не подписаны, потому что:
 \begin{itemize}
  \item Номер состояния \emph{полностью} описывает состояние программы
  \item Если переход условный - надо поделить состояние на два
  \begin{itemize}
    \item То, в котором условие верно (переход \emph{может} произойти)
    \item То, в котором условие неверно (переход \emph{не может} произойти)
  \end{itemize}
  \item Программу \emph{можно} странслировать в структуру Крипке
  \item Структуры Крипке прекрасно поддаются верификации 
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{LTL}
 Линейная темпоральная логика (Linear Temporal Logic).

 Рассуждает о последовательностях состояний мира во времени.

 \begin{itemize}
  \item Есть запрос $\Rightarrow$ когда-нибудь будет ответ
  \item Блокировка запрошена $\Rightarrow$ клиент будет обслужен сколь угодно большое число раз, пока не отпустит ее
  \item \ldots
 \end{itemize}

  Прелести:
  \begin{itemize}
   \item Краткая, понятная, мощная и однозначная
   \item LTL-свойства легко верифицируются даже вручную
   \oneitem{Относительно структур Крипке}
   \item Много мощных инструментов
  \end{itemize}

\end{frame}

\begin{frame}
 \frametitle{Формулы LTL}

 \begin{description}
  \item[$p_1,p_2,\ldots$] Переменные
  \item[$A \wedge B, \neg A\ldots$] Логические связки
  \item[$X A$] В следующий момент $A$ (neXt)
  \item[$G A \equiv \square A$] Всегда $A$ (Globally)
  \item[$F A \equiv \Diamond A$] Когда-нибудь $A$ (Future)
  \item[$A \mathcal{U} B$] $A$, по крайней мере до наступления $B$
 \end{description}
\end{frame}

\begin{frame}
 \frametitle{Бесконечности}
 \begin{itemize}
  \item Начиная с некоторого момента, навсегда: $FG~A \equiv \Diamond \square A$
  \item Бесконечно часто: $GF~A \equiv \square \Diamond A$
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Иллюстрация формул LTL}
 \begin{center}
  \includegraphics[scale=0.5]{ltl.pdf}
 \end{center}
\end{frame}

\begin{frame}
 \frametitle{Свойства}
 \begin{itemize}
  \item Живость (liveness)
  \oneitem{Что-то хорошее когда-нибудь произойдет: $\Diamond Alive$}
  \item Безопасность (safety)
  \oneitem{Что-то плохое никогда не произойдет: $\square \neg Dead$}
  \item Справедливость (fairness)
  \begin{itemize}
    \item То, что может произойти - произойдет
    \item Слабая: $\Diamond \square Req \to \square \Diamond Ack$
    \item Сильная: $\square \Diamond Req \to \square \Diamond Ack$
    \item Антоним - starvation (голодание)
  \end{itemize}
 \end{itemize}
\end{frame}

\begin{frame}[fragile]
 \frametitle{Примеры LTL-свойств}
 \begin{block}{Пример 1}
  $\square$ (state==OFF) $\to$ \\
  \qquad (state==OFF $\mathcal{U}$ turnOnIsCalled)
 \end{block}
 \begin{block}{Пример 2}
  $\square$ (req\_interrupt $\to$ \\
  \qquad $\Diamond$ $\square$ (state==COMPLETED $\vee$ state==INTERRUPTED))
 \end{block}
\end{frame}

\begin{frame}
 \frametitle{Model checking}
 Наука о проверке свойств программ (например, LTL) на основе их моделей (например, структур Крипке) - \emph{Model checking}

 Премия Тьюринга 2007 - за достижения в области model checking, сделавшие его применимым для проектов реального размера.
\end{frame}


\begin{frame}
 \frametitle{Инструмент: SPIN}
 Язык + верификатор LTL-свойств для параллельных программ.

 Лауреат ACM Software System award (2001) (другие лауреаты: Unix, TeX, Java, Apache, TCP/IP, \ldots).

 \begin{itemize}
  \item Си-подобный синтаксис
  \item Для нарушенных свойств генерируется нарушающая их трасса
  \item (уродливый, но терпимый) GUI
  \item Я проверял: Пригодно для применения на практике.
 \end{itemize}

 \link{http://spinroot.com/spin/whatispin.html} - официальный сайт.
\end{frame}

\begin{frame}
 \frametitle{Инструмент: J-LO}
 Задаем LTL-свойства, они проверяются в рантайме.
 \begin{itemize}
  \item Аннотация \texttt{@LTL("...")}
  \item Инструментирование байткода
 \end{itemize}
 

 \begin{block}{Пример}
   (!call(void Foo.doWork())) U (call(Foo.init()))
 \end{block}
\end{frame}

\begin{frame}[fragile]
 \frametitle{Пример пожестче}
  Lock reversal.
  \begin{Verbatim}[fontsize=\tiny]
   pointcut lock(Thread t, Lock l):
     call(Lock.lock(Thread)) && args(t) && target(l);
   pointcut unlock(Thread t, Lock l):
     call(Lock.unlock(Thread)) && args(t) && target(l);
   Thread i,j; Lock x,y;
   !lock(i,y) U (lock(i,x) /\ (!unlock(i,x) U (lock(i,y) /\ !target(x))))
   -> G !(!lock(j,x) U (lock(j,y) /\ !args(i) /\ (!unlock(j,y) U lock(j,x) )))
  \end{Verbatim}
\end{frame}

\begin{frame}
 \frametitle{AspectJ+LTL}
 \link{http://www.sable.mcgill.ca/~ebodde/rv/JLO/} - сайт тулы.
 \begin{block}{Кстати}
  The work is based on a Haskell-prototype developed at our department.
 \end{block}

 \link{http://abc.comlab.ox.ac.uk/extensions} - Tracecheck: похожая тула от тех же авторов: проверяет регулярные выражения над трассами программы.
\end{frame}


\begin{frame}
 \frametitle{Model checking:further reading}
  \link{http://www.inf.unibz.it/~artale/FM/slide3.pdf}

туториал по LTL.

  \link{http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.60.3062}

статья про J-LO

  \link{http://spinroot.com/spin/Doc/course/mc-tutorial.pdf}

Model Checking: A tutorial overview (много ссылок)
\end{frame}

\subsubsection{Thread safety}

\begin{frame}
 \frametitle{Ближе к делу}
 Что брать за аксиомы в реальных программах?
 \begin{itemize}
  \item Thread safety
  \item Java memory model
 \end{itemize}
\end{frame}


\begin{frame}
 \frametitle{Thread safety}
 Понимайте, формулируйте и документируйте ее, иначе не из чего будет делать выводы о корректности.
 \begin{itemize}
  \item \alert{Immutable.} У объекта всего 1 состояние.
  \item \alert{Thread-safe.} Каждая операция сама по себе безопасна/атомарна. Вместе - нет.
  \begin{itemize}
   \item Последовательности операций нужно координировать извне
   \item Документируйте, какие \emph{именно} последовательности все-таки безопасны
   \item Пример: Банковский счет
  \end{itemize}
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Thread safety}
 \begin{itemize}
  \item \alert{Conditionally thread-safe.} Почти как Thread-safe.
  \oneitem{Но есть хотя бы один метод, бесполезный ``в одиночку''}
  \item \alert{Thread-compatible.} Можно использовать многопоточно, если не вызывать операции одновременно.
  \oneitem{Для всего нужна внешняя синхронизация, но с ней будет работать}
  \item \alert{Thread-hostile.} Вообще нельзя использовать многопоточно.
  \item \alert{Thread-confined.} Можно использовать из одной \emph{конкретной} нити.
  \oneitem{Пример: Swing/AWT}
 \end{itemize}
\end{frame}

\subsubsection{Java memory model}
\begin{frame}
 \frametitle{Java Memory Model}
 Грубо: Набор аксиом о том, какие происшествия в памяти кому и когда видимы.
 \begin{itemize}
   \item Чтобы компилятор мог выполнять оптимизации
   \oneitem{Переупорядочение, удаление дохлого кода \ldots}
   \item Чтобы можно было эффективно использовать кэши, особенно в многопроцессорных системах.
 \end{itemize}
\end{frame}

\begin{frame}[fragile]
 \begin{block}{Пример}
  \begin{Verbatim}[fontsize=\small]
    private int x, y;

    void foo() {
        x = 5;
        y = 7;
    }

    void bar() {
        if(x==5) {
           // Неверно, что y==7
        }
    }
  \end{Verbatim}
 \end{block}
\end{frame}


\begin{frame}[fragile]
 \frametitle{final поля и JMM}
 \begin{block}{Пример}
  \begin{Verbatim}
   public final class Foo {
       private int x;
       Foo(int x) {this.x = x;}
       int getX() {return x;  }
   }
  \end{Verbatim}
 \end{block}
 \alert{Не thread-safe!} x должен быть final.
\end{frame}

\begin{frame}
 \frametitle{Java Memory Model}
 Более точно: Набор аксиом о том, какие \emph{наблюдения} результатов последовательности действий в памяти - возможны.

 Цели:
 \begin{itemize}
  \item Безопасность
  \oneitem{Безопасная инициализация}
  \item Интуитивность
  \item Эффективная реализуемость
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Java Memory Model}
 Влияющие факторы:
 \begin{itemize}
  \item \texttt{synchronized}
  \item \texttt{volatile}
  \item \texttt{final}
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Java Memory Model}
 Основные понятия:
 \begin{itemize}
  \item Действие
  \begin{itemize}
   \item Обращение к разделяемым переменным
   \item Вход/выход из монитора
   \item Запуск/ожидание нитей
  \end{itemize}

  \item Видимость
  \item Отношение \emph{happens-before}
  \begin{itemize}
   \item Жизнь 1 нити упорядочена
   \item Жизнь 1 монитора упорядочена
   \item Жизнь 1 volatile переменной упорядочена
  \end{itemize}
 \end{itemize}
\end{frame}

\begin{frame}[fragile]
 \frametitle{Что все-таки делает volatile?}
 Чтение \emph{одной} volatile переменной - почти точка синхронизации.

 \begin{Verbatim}
  class VolatileExample {
      int x = 0;
      volatile boolean v = false;
      public void writer() {
          x = 42; v = true;
      }

      public void reader() {
          if (v == true) { /* x==42 */ }
      }
  }
 \end{Verbatim}
\end{frame}

\begin{frame}
 \frametitle{Что все-таки делает final?}
 После конструирования \texttt{final} поля \emph{видимы}.
 \begin{itemize}
  \item Видимы также объекты, доступные через них
  \item Ссылка на объект не должна утекать из конструктора
  \begin{itemize}
   \item Регистрация листенером, присваивание статического поля...
   \item Делайте это после конструирования.
  \end{itemize}
 \end{itemize}
\end{frame}

\subsubsection{Статический анализ}
\begin{frame}[fragile]
 \frametitle{CheckThread}
 Набор аннотаций для документирования thread safety.

 Есть плагин к IDEA.

 Очень полезно.

 \begin{block}{Пример}
  \begin{semiverbatim}
  {\color{red}@ThreadSafe} class SynchronizedInteger \{
    {\color{red}@GuardedBy("this")} private int value;
    synchronized int get()       \{ return value; \}
    synchronized void set(int v) \{ value = v;    \}
  \}
  \end{semiverbatim}
 \end{block}
\end{frame}

\begin{frame}
 \frametitle{Java Path Finder}
 Виртуальная машина, умеющая символьно выполнять Java-код и верифицировать свойства \emph{для всех возможных запусков с учетом многопоточности}. Сделано в NASA.

 \link{http://javapathfinder.sourceforge.net/}

 \link{http://sourceforge.net/projects/visualjpf/} - GUI

 \link{http://www.visserhome.com/willem/presentations/ase06jpftut.ppt} - подобие туториала

 \begin{itemize}
  \item Утверждается, что справляется с проектами до 10KLOC.
  \item Находил баги в NASA-овском софте (в марсоходе, например)
  \item Основан на SPIN
  \item Есть ant-task и плагин к eclipse; расширяем
 \end{itemize}

 Я написал маленький пример с дедлоком. Сработало.
\end{frame}


\begin{frame}
 \frametitle{Другие тулы}
 Статический анализ многопоточных ошибок есть и в:
 \begin{itemize}
  \item PMD
  \item FindBugs (есть плагин к IDEA)
 \end{itemize}
 Проверено: помогает (и не только от многопоточных).
\end{frame}


\subsection{Улучшение корректности}

\begin{frame}
 \frametitle{Философское избавление от багов}
 Надо уменьшить $O(K^N)$.
 \begin{itemize}
  \item Уменьшить число наблюдаемых состояний ($K$)
  \begin{itemize}
    \item Immutability
    \item Инкапсуляция состояния
    \item Синхронизация
    \item Крупные операции (\texttt{incrementAndGet}, \texttt{putIfAbsent})
  \end{itemize}
  \item Навязать трассам эквивалентность
  \begin{itemize}
    \item Идемпотентные операции
    \oneitem{\texttt{foo();foo();} $\sim$ \texttt{foo();}}
    \item Коммутативные (независимые) операции
    \oneitem{\texttt{foo();bar();} $\sim$ \texttt{bar();foo();}}
    \oneitem{В т.ч. инкапсуляция и независимые объекты}
  \end{itemize}
 \end{itemize}
\end{frame}

\subsubsection{Immutability}
\begin{frame}
 \frametitle{Immutability}
 Нельзя изменить \emph{вообще} $\Rightarrow$ нельзя изменить \emph{неправильно, не в том порядке} \ldots
 \begin{itemize}
  \item Все поля \alert<1>{private}, \alert<2>{final}, и их классы \alert<3>{сами по себе immutable}
  \begin{itemize}
    \item \alert<1>{Иначе поле может изменить кто-то другой}
    \item \alert<2>{Иначе нарушится thread safety (см.сл.слайд)}
    \item \alert<3>{Иначе изменение может произойти ``тайком''}
  \end{itemize}
  \item \alert<4>{Сам класс final}
  \begin{itemize}
    \item \alert<4>{Иначе можно создать mutable потомка и передать его кому-нибудь в качестве объекта базового класса}
  \end{itemize}
  \item \alert<5>{Базовый класс тоже immutable}
  \begin{itemize}
    \item \alert<5>{Иначе можно изменить состояние при помощи операций базового класса}
  \end{itemize}
 \end{itemize}
\end{frame}

\subsubsection{Инкапсуляция состояния}

\begin{frame}
 \frametitle{Инкапсуляция состояния}
 Программа корректна ровно настолько, насколько корректны \alert{и скоординированы} все, кто \emph{могут} повлиять на состояние объекта.

 Мораль:
 \begin{itemize}
  \item Чем меньше способов повлиять на состояние, тем лучше.
  \item Независимые задачи - выносить в независимые объекты
 \end{itemize}
\end{frame}

\begin{frame}[fragile]
 \frametitle{Инкапсуляция состояния}
 \begin{Verbatim}
 class DataLoader {
    ClientToken beginLoad(Client client);
    void writeData(ClientToken token, Data data);
    void commit(ClientToken token);
    void rollback(ClientToken token);
 }
 \end{Verbatim}
\end{frame}

\begin{frame}
 \frametitle{Инкапсуляция состояния}
 Сложный код:
 \begin{itemize}
  \item Соответствие \texttt{ClientToken}/транзакция
  \item (многопоточные клиенты) \texttt{synchronized(locks.get(token))}
 \end{itemize}
\end{frame}

\begin{frame}[fragile]
 \frametitle{Инкапсуляция состояния}
 Разорвем лишнюю зависимость между независимыми задачами.
 \begin{Verbatim}
 class DataLoader {
    PerClientLoader beginLoad(Client client);
 }
 class PerClientLoader {
    void writeData(Data data);
    void commit();
    void rollback();
 }
 \end{Verbatim}
\end{frame}

\begin{frame}
 \frametitle{Инкапсуляция состояния}
 \begin{itemize}
  \item Простой и незагрязненный код
  \item Синхронизация простым \texttt{synchronized}
  \item Никаких таблиц
  \item Никаких проблем с охраной таблиц от многопоточного доступа
 \end{itemize}
\end{frame}

\subsubsection{Синхронизация}

\begin{frame}[fragile]
 \frametitle{Синхронизация (сериализация доступа)}
 Это все знают: ``Хочешь защитить объект - сделай на нем \texttt{synchronized}''.
\end{frame}


\begin{frame}[plain]
 \includegraphics[scale=0.5]{deadlock.pdf}
\end{frame}



\begin{frame}[fragile]
 \frametitle{Синхронизация (сериализация доступа)}
 Если надо защитить доступ к комбинации объектов - надо синхронизироваться \emph{в одинаковом порядке}.

 Иначе - дедлоки.

 \begin{block}{Так делать не надо}
 \begin{Verbatim}[fontsize=\tiny]
  void foo() {
    synchronized(x) {
      synchronized(y) {
        ...
      }
    }
  }
  void bar() {
    synchronized(y) {
      synchronized(x) {
        ...
      }
    }
  }
 \end{Verbatim}
 \end{block}
\end{frame}

\begin{frame}[fragile]
 \frametitle{Борьба с дедлоками}
 Нужен глобально фиксированный порядок блокировок.
 ``Экзотический'' случай:
 \begin{block}{Так делать не надо}
 \begin{Verbatim}
  void transfer(Account from,Account to,int money) {
    synchronized(from) {
      synchronized(to) {
        ..
      }
    }
  }
 \end{Verbatim}
 \end{block}
\end{frame}

\begin{frame}[fragile]
 \frametitle{Борьба с дедлоками: Экзотический случай}
  Нужен глобально фиксированный порядок блокировок.
  \begin{block}{Надо делать вот так}
  \begin{Verbatim}
  void transfer(Account from,Account to,int money) {
    synchronized(from<to ? from : to) {
      synchronized(from?to ? to : from) {
        ..
      }
    }
  }
  \end{Verbatim}
  \end{block}
  Подробно - см. Java Concurrency in Practice.
\end{frame}

\begin{frame}[fragile]
 \frametitle{Еще немного о дедлоках}
 Не стоит вызывать чужие методы (callbacks), держа блокировку (``alien call'').
 Такие вызовы лучше превратить в ``open call'' (вызов вне блокировки)
 \begin{Verbatim}[fontsize=\tiny]
  private void frobbleBar(Bar bar) {
      List<BarListener> copy;
      synchronized (this) {
         copy = new ArrayList<BarListener>(listeners);
      }
      for (Listener l : snapshot)
         l.barFrobbled(bar);
  }
 \end{Verbatim}
 Более общий случай:
 \oneitem{Минимизируйте сложность и ``неизвестность'' кода внутри блокировки}
\end{frame}

\begin{frame}
 \frametitle{Еще немного о дедлоках}
 Частая причина дедлоков - ресурсы и пулы.
 \begin{itemize}
  \item Доступ к ресурсам надо упорядочивать, как и блокировки
  \item Пулы + взаимозависимые задачи = проблема Thread starvation deadlock
  \begin{itemize}
   \item Пул забит нитями, ждущими результата вычисления
   \item Вычисление в очереди, но его некому начать - пул забит
  \end{itemize}
 \end{itemize}
\end{frame}

\begin{frame}[fragile]
 \frametitle{Синхронизация и наследование}

 Очень трудно сделать эффективный thread-safe класс на основе non-thread-safe базового.

 \begin{itemize}
  \item Придется перегрузить и синхронизировать \emph{все до единой} операции
  \item В т.ч. и длительные, тяжеловесные
  \item Не дай бог какие-то из операций \texttt{final}
 \end{itemize}

 Как с наследованием:
 \begin{itemize}
  \item ``Design for inheritance or prohibit it''
  \item ``Design for thread-safety''
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Синхронизация и наследование}
 Паттерн ``Thread-safe interface'':
 \begin{itemize}
  \item Поделите компонент на 2 части - методы интерфейса и методы реализации
  \item Методы интерфейса выполняют синхронизацию
  \item Методы реализации вызывают \emph{только} другие методы реализации
 \end{itemize}

\end{frame}


\subsubsection{Крупные операции}

\begin{frame}
 \frametitle{Крупные операции}
 Идеальный способ избавить клиентов от необходимости координировать последовательность вызовов - сделать, чтобы им не надо было делать \emph{последовательность} вызовов.
 \begin{itemize}
  \item \texttt{AtomicInteger.getAndIncrement}
  \item \texttt{ConcurrentMap.putIfAbsent}
  \item \texttt{Bank.transfer}
 \end{itemize}
 Достаточно правильно реализовать саму операцию. Проектируйте API в таком стиле, если это возможно.
\end{frame}

\begin{frame}
 \frametitle{Крупные операции}
 Частный случай:
 \begin{itemize}
  \item У объекта в меру большое состояние
  \item Хочется атомарно поменять несколько его частей
  \item Запихните состояние в объект и поменяйте атомарно ссылку на этот объект
  \oneitem{\texttt{AtomicReference}}
 \end{itemize}
 \link{http://tobega.blogspot.com/2008/03/java-thread-safe-state-design-pattern.html}
\end{frame}


\subsubsection{Идемпотентные операции}

\begin{frame}
 \frametitle{Идемпотентные операции}
 \texttt{foo();foo();} $\sim$ \texttt{foo();}

 Если это так, то можно не предпринимать мер по ограничению числа вызовов \texttt{foo()}.

 Особенно важно в распределенных и веб-системах (с ненадежным подтверждением вызова \texttt{foo()}).

 Частый пример - ленивая инициализация.
\end{frame}

\begin{frame}
 \frametitle{Идемпотентные операции}
\begin{itemize}
  \item \texttt{set.add(x)} - идемпотентна
  \item \texttt{x.setFoo(foo)} - идемпотентна
  \item \texttt{list.add(x)} - не идемпотентна
  \item \texttt{/buy.php?product\_id=123} - не идемпотентна
 \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Идемпотентные операции}
  Достижение идемпотентности:
 \begin{itemize}
  \item Присвоить каждому вызову операции уникальный \texttt{id}
  \item Если такой \texttt{id} уже был - это дубль
  \item Актуально в вебе.
 \end{itemize}
\end{frame}

\subsubsection{Абстрагирование}

\begin{frame}
 \frametitle{Абстрагирование}

 Многопоточную программу намного легче отладить, если в ней нет ничего, кроме самой сути.

 Баги вылезают на поверхность, нет соблазна сказать ``В нашей задаче такая ситуация невозможна''.

 \begin{itemize}
  \item Не ``блокировка индекса на чтение или запись'', а просто ``блокировка на чтение или запись''
  \item Не ``очередь e-mail'ов'', а ``отказоустойчивая очередь задач''
  \item Не ``параллельный подсчет слов'', а MapReduce
  \item Не ``параллельная фильтрация массива'', а ParallelArray
 \end{itemize}

 Может оказаться, что такая штука уже есть.
\end{frame}

\begin{frame}
 \frametitle{Абстрагирование}

 А какие штуки уже есть?

 Об этом - позже.
\end{frame}


\section{Тестирование}

\begin{frame}
 \frametitle{Тестирование}
 Тестировать многопоточный код адски сложно.
 \begin{itemize}
  \item Протестировать правильность детерминированного кода - можно, хоть и трудно
  \item Протестировать отсутствие багов, связанных с недетерминизмом - совсем сложно
  \item Нет контроля над главным фактором трудноуловимых ошибок - недетерминизмом шедулера
  \item Необходимо статистическое тестирование
  \begin{itemize}
    \item И даже оно \emph{ничего} не гарантирует
    \item Лучше, конечно, доказывать корректность
  \end{itemize}
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Тестирование}
 Что нужно оттестировать?
 \begin{itemize}
  \item Код последовательно корректен
  \item Код правильно работает без нагрузки
  \item Код не ломается под нагрузкой
 \end{itemize}
 Именно в таком порядке.
\end{frame}

\begin{frame}
 \frametitle{Наличие ожидаемого поведения}
 Как проверить, что многопоточный код реализует определенный протокол в ``идеальных'' условиях?
 \begin{itemize}
  \item Понаставить задержек, тем самым сделав порядок событий детерминированным
  \item Проверить, что происходят нужные события в нужном порядке
  \begin{itemize}
    \item Проверять, что блокирующие вызовы - блокируются
    \item Проверять, что неблокирующие вызовы - не блокируются
    \item Mock objects, listeners во всех важных точках кода
  \end{itemize}
 \end{itemize}
 Криво, длинно, уродливо, но работает.
\end{frame}

\begin{frame}
 \frametitle{Устойчивость к нагрузке}
 Как проверить, что многопоточный код не ломается под нагрузкой?
 \begin{itemize}
  \item Придумать инварианты
  \item Организовать нагрузку
  \item Постоянно проверять инварианты
 \end{itemize}
 Криво, длинно, уродливо, ничего не гарантирует, но может выявить ошибку.
 \oneitem{Повторить или отладить ее будет почти невозможно}
\end{frame}

\begin{frame}
 \frametitle{Устойчивость к нагрузке}
 Пример: Тестируем \texttt{ConcurrentMap}.
 \begin{itemize}
  \item Инвариант: Каждый добавленный, но не удаленный элемент присутствует в мапе
  \item Инвариант: \texttt{size()} равно числу добавленных, но не удаленных элементов.
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Устойчивость к нагрузке}
 Пример: Тестируем \texttt{ConcurrentMap}
 \begin{itemize}
  \item Повторить 100000000000000 раз
   \begin{itemize}
    \item Сгенерировать 10000 случайных значений, разбить на 10 частей случайным образом
    \item В 10 нитей:
    \begin{itemize}
      \item добавлять в мапу значения из i-й части со случайными небольшими задержками
      \item проверять, что все предыдущие значения из i-й части в мапе есть
    \end{itemize}
    \item По окончании проверить наличие каждого значения
    \item Пригодится \texttt{CyclicBarrier}
   \end{itemize}
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Повторяемость}
 Как повторить готовую ошибку?
 \begin{itemize}
  \item Написать делегирующие mock-объекты, записывающие все действия
  \item Дождаться ошибки
  \item Написать mock-объекты, ``проигрывающие'' заданный сценарий
 \end{itemize}
 Поможет найти ``гонки'' в протоколе.
 \alert{Не поможет} найти низкоуровневые ``гонки'' (между statement'ами).
 \oneitem{Без мозгов не обойтись!}
\end{frame}

\begin{frame}
 \frametitle{Как спровоцировать ошибку}
 Как организовать максимум недетерминизма шедулера?
 \begin{itemize}
  \item Понаставить \texttt{Thread.yield()} или \texttt{Thread.sleep(1)} в разных местах кода
  \item Использовать $\approx 2*NCPU$ нитей
  \oneitem{Чтобы и все CPU были заняты, а нити и вытеснялись, и не простаивали слишком долго}
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Тулы}
 \begin{itemize}
  \item TestNG имеет небольшие специальные средства
  \oneitem{\tiny{\texttt{@Test(threadPoolSize=5,invocationCount=10,threadMap={2,2,2,3,1})}}}
  \item MultithreadedTC (\link{http://code.google.com/p/multithreadedtc/})
  \begin{itemize}
    \item \texttt{assertTick(n), waitForTick(n)}
    \item Понаставить тиков можно только в тестовом коде
  \end{itemize}
  \item Упомянутый J-LO, tracecheck \ldots
 \end{itemize}
\end{frame}



\section{Готовое и известное}

\begin{frame}
 \frametitle{Модели многопоточных вычислений}
 Параллелизм:
 \begin{itemize}
  \item MapReduce: Огромные объемы данных, распределенная обработка
  \item Fork/Join: Задачи с рекурсивной структурой
  \item Векторные модели: huge-scale SIMD
  \item Конвейер / data flow
  \item \ldots
 \end{itemize}
 Concurrency:
 \begin{itemize}
  \item Message-passing (actor model)
  \item Event loop (message-passing с одним / одинаковыми акторами)
  \oneitem{Сервера, подавляющее большинство GUI-библиотек, в т.ч. Swing}
  \item Software Transactional Memory
 \end{itemize}
\end{frame}

\subsection{Параллелизм}

\begin{frame}
 \frametitle{MapReduce}
 Слишком известно, чтобы на нем останавливаться

 Реализация для Java: Hadoop
\end{frame}

\begin{frame}[fragile]
 \frametitle{Fork/Join}
 \begin{Verbatim}
  if(isSmall(problem)) {
      return solveSequentially(problem);
  } else {
      // Fork
      List<Problem> subproblems = split(problem);
      List<Result> res = parallelMap(solve, subproblems);
      // Join
      return combine(res);
  }
 \end{Verbatim}
\end{frame}


\subsubsection{Fork/Join}

\begin{frame}
 \frametitle{Fork/Join}
 Пример: Шахматы. Предпросмотр на n шагов.
 \begin{itemize}
  \item \texttt{n==0} $\Rightarrow$ оценить позицию
  \item Fork: По подзадаче на каждый ход
  \item Join: Выбрать ход с самой высокой оценкой
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Fork/Join}
 Пример: Интегрирование.
 \begin{itemize}
  \item Интервал мал $\Rightarrow$ проинтегрировать влоб
  \item Fork: по подзадаче на обе половины интервала
  \item Join: сложить результаты
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Fork/Join}
 Пример: Умножение матриц: $C += AB$ (В т.ч. поиск путей в графах и т.п.)
 \begin{itemize}
  \item $A$ и $B$ малы $\Rightarrow$ влоб
  \item Fork: Поделить $A$ на верх/низ и $B$ на лево/право
  \item Join: Ничего, просто дождаться результатов Fork
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Fork/Join}
 \begin{center}
  \includegraphics[scale=0.5]{matrix.pdf}
 \end{center}
\end{frame}

\begin{frame}[fragile]
 \frametitle{Fork/Join in JDK7}
 Примерно так. Официального окончательного Javadoc до сих пор нет.
 \begin{Verbatim}[fontsize=\tiny]
  class Solver extends RecursiveAction {
      private final Problem problem;
      int result;
      protected void compute() {
          if (problem.size < THRESHOLD) {
              result = problem.solveSequentially();
          } else {
              int m = problem.size / 2;
              Solver left, right;
              left = new Solver(problem.subProblem(0, m));
              right = new Solver(problem.subProblem(m, problem.size));
              forkJoin(left, right);
              result = //get the result from left right
          }
      }
  }
  ForkJoinExecutor pool = new ForkJoinPool(
    Runtime.availableProcessors());
  Solver solver = new Solver(new Problem());
  pool.invoke(solver);
 \end{Verbatim}
\end{frame}


\subsubsection{Векторные алгоритмы}

\begin{frame}
 \frametitle{Векторные алгоритмы}

 Huge-scale SIMD: Примитивные операции оперируют сразу над большими массивами.
 \begin{itemize}
  \item Map: Применение функции к каждому элементу / склейка $N$ массивов по $N$-арной операции
  \item Fold: Ассоциативная свертка в моноиде.
\begin{align*}
\mbox{$\star$ ассоциативна:}\quad & a \star (b \star c)=(a \star b) \star c \\
\mbox{$u$ - единица $\star$:}\quad & a \star u=u \star a=a
\end{align*}
$$fold\ \star\ u\ [x_0,x_1,\ldots,x_n] = u \star x_0 \star x_1 \star \ldots \star x_n$$
  \item Scan (Prefix sum): Пробег (Префиксная сумма)
$$scan\ \star\ u\ [x_0,x_1,\ldots,x_n] = [u, u \star x_0, u \star x_0 \star x_1, \ldots, u \star \ldots \star x_n]$$
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Векторные модели}
 Прелести:
 \begin{itemize}
  \item Свертка параллелизуется: Ускорение $O(P/log P)$ на $P$ процессорах
  \item Пробег так же параллелизуется
  \item Удивительно мощные и универсальные операции
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Префиксные суммы}
 Что можно сделать сверткой/пробегом (т.е. параллельно):
 \begin{itemize}
  \item sum,min,max,avg,\ldots
  \item Radix sort, Quicksort
  \item Сложение длинных чисел
  \item Выпуклая оболочка
  \item Многие алгоритмы на графах
  \item Многие рекуррентные последовательности n-го порядка
  \item Трехдиагональные системы уравнений
  \item \ldots
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Префиксные суммы}
 Особенно интересно, \emph{как} это делается. Базовые операции поверх пробега:
 \begin{itemize}
  \item Рекуррентная последовательность 1го порядка
  \item Упаковка массива
  \item Сортировка массива по 1-битному флагу (``разбиение'')
  \item Сегментированный пробег (пробег со сбросами)
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Префиксные суммы}
 Упаковка массива (``pack'', ``filter'').
 \begin{center}
  \includegraphics[scale=0.5]{vpack.pdf}
 \end{center}
\end{frame}

\begin{frame}
 \frametitle{Префиксные суммы}
 Сортировка по 1-битному флагу (``разбиение'', ``partition'').
 \begin{center}
  \includegraphics[scale=0.5]{vpart.pdf}
 \end{center}

 Radixsort тривиален.
\end{frame}

\begin{frame}
 \frametitle{Префиксные суммы}
 Сегментированный пробег (Segmented scan).
 \begin{center}
  \includegraphics[scale=0.5]{vsegscan.pdf}
 \end{center}
 Позволяет реализовать рекурсию без рекурсии.
\end{frame}

\begin{frame}
 \frametitle{Префиксные суммы}
 В целом - красивый, мощный, простой в реализации и необычный векторный ``язык''.

 Часто используют на GPU.

 \link{http://sourceforge.net/projects/amino-cbbs/} - реализация на Java (содержит много других готовых параллельных алгоритмов).

 \link{http://www.cs.cmu.edu/~blelloch/papers/Ble90.pdf} - прекрасная книга Vector models for data-parallel computing. Строжайше рекомендую.
\end{frame}

\begin{frame}
 \frametitle{ParallelArray}
 New in JDK7. Реализация некоторых векторных примитивов поверх Fork/Join framework.

 \begin{itemize}
  \item Стандартные: Map, Zip, Filter, Fold (\texttt{reduce}), Scan (\texttt{cumulate} + \texttt{precumulate}), Sort
  \item Поинтереснее: Сечение по диапазону (\texttt{withBounds}), Перестановка (\texttt{replaceWithMappedIndex})
  \item Функциональный до мозга костей API (подавляющее большинство функций - ФВП)
  \oneitem{Правда, без фанатичного следования функциональной чистоте}
  \item Ленивые операции
  \item Сплавка операций (\emph{fusion})
 \end{itemize}
\end{frame}

\begin{frame}[fragile]
 \frametitle{ParallelArray}
 Примерчик.

 \begin{Verbatim}[fontsize=\tiny]
    ParallelArray<Student> students = new ParallelArray<Student>(fjPool, data);
    double bestGpa = students.withFilter(isSenior)
                             .withMapping(selectGpa)
                             .max();

    public class Student {
        String name;
        int graduationYear;
        double gpa;
    }

    static final Ops.Predicate<Student> isSenior = new Ops.Predicate<Student>() {
        public boolean op(Student s) {
            return s.graduationYear == Student.THIS_YEAR;
        }
    };
    static final Ops.ObjectToDouble<Student> selectGpa = new Ops.ObjectToDouble<Student>() {
        public double op(Student student) {
            return student.gpa;
        }
    };
 \end{Verbatim}
\end{frame}

\subsection{Concurrency}

\subsubsection{Message-passing}

\begin{frame}
 \frametitle{Message-passing concurrency}
 Фактически единственно возможный подход в распределенных системах.
 \begin{itemize}
  \item Вообще нету разделяемого состояния
  \item \emph{Акторы} обмениваются \emph{сообщениями}
  \item У каждого актора есть mailbox (FIFO-очередь сообщений)
  \item Отсылка сообщений асинхронная и неблокирующая
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Message-passing concurrency}
 \begin{itemize}
  \item Не панацея: дедлоки никуда не деваются, просто они другие
  \item Тем не менее, написать корректную программу - проще
  \item Есть формальные модели $\Rightarrow$ поддается верификации
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Message-passing concurrency}
 Реализации:
 \begin{itemize}
  \item Куча языков: MPI
  \item Termite Scheme
  \item Clojure: agents
  \begin{itemize}
  \item Очень интересная и мощная вариация. Definitely worth seeing. \link{http://clojure.org/agents}
  \item ``Clojure is to concurrent programming as Java was to OOP''
  \end{itemize}
  \item Scala: actors
  \item Java: Kilim
  \item И, конечно, Erlang
  \oneitem{Killer feature: Selective receive}
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Message-passing concurrency}
 Kilim: 
 \begin{itemize}
  \item Легковесные нити (1млн в порядке вещей; 1000x faster)
  \item Очень быстрый message passing (утверждается, что 3x Erlang)
  \item Постпроцессит байт-код (CPS transform для методов, аннотированных \texttt{@pausable}).
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Message-passing concurrency}
 \link{http://kilim.malhar.net/} (в данный момент лежит \ldots)

 \link{http://www.cl.cam.ac.uk/research/srg/opera/publications/papers/kilim_ecoop08.pdf} - научная статья. Не для робких, но читать можно. Много интересных идей.

 \link{http://eprints.kfupm.edu.sa/30514/1/30514.pdf} - оригинальная книга Тони Хоара про Communicating Sequential Processes - теоретическая основа message-passing
\end{frame}

\subsubsection{Event loop}

\begin{frame}
 \frametitle{Event loop}
 Вариация на тему message passing, но - не много взаимодействующих акторов, а один (или несколько одинаковых) жирный и всемогущий.
 \begin{itemize}
  \item Серверы (и \texttt{accept}, и \texttt{select/poll/\ldots} сюда относятся)
  \item GUI-фреймворки
 \end{itemize}
 Прелести:
 \begin{itemize}
  \item Это не фреймворк, но паттерн: легко реализовать и использовать даже на микроуровне
  \item К нему сводится куча задач
  \item Очень легко пишется
  \item Большинство многопоточных проблем отсутствуют
 \end{itemize}
\end{frame}

\begin{frame}[fragile]
 \frametitle{Event loop}
 \begin{Verbatim}
  private BlockingQueue<OurEvent> events =
    new LinkedBlockingQueue<OurEvent>();

  void mainLoop() {
      while(true) {
          processEvent(events.poll());
      }
  }

  public class OurEvent {...}
 \end{Verbatim}
\end{frame}


\subsubsection{Software Transactional Memory}

\begin{frame}
 \frametitle{Software Transactional Memory}
 Транзакции на уровне памяти; атомарные куски кода.
 \begin{itemize}
  \item Полноценный commit/rollback, полная атомарность
  \item Транзакции \emph{повторяемы}
  \item \alert{Транзакционные программы комбинируемы!}
  \oneitem{В отличие от shared state (правильно+правильно$\neq$правильно)}
  \item Не должно быть \emph{никаких} побочных эффектов, кроме обращений к транзакционной памяти
 \end{itemize}
\end{frame}

\begin{frame}[fragile]
 \frametitle{Software Transactional Memory}
 Псевдокод:
 \begin{Verbatim}
   // Insert a node into a doubly-linked list atomically
   atomic {
       newNode->prev = node;
       newNode->next = node->next;
       node->next->prev = newNode;
       node->next = newNode;
   }
 \end{Verbatim}
\end{frame}

\begin{frame}[fragile]
 \frametitle{Software Transactional Memory}
 Псевдокод (впервые предложено в реализации в Haskell):
 \begin{Verbatim}
   atomic {
       if (queueSize > 0) {
           remove item from queue and use it
       } else {
           retry
       }
   }
 \end{Verbatim}
 \texttt{retry} перезапускает транзакцию в момент, когда изменится одна из \emph{прочитанных} ею переменных.
\end{frame}

\begin{frame}
 \frametitle{Software Transactional Memory}
 Реализации:
 \begin{itemize}
  \item Haskell: полноценная и безопасная поддержка
  \item Clojure: полноценная и небезопасная поддержка
  \item Java: Deuce, JSTM, \ldots
  \item Много библиотек для C и C++, в т.ч. даже компиляторы с ключевым словом \texttt{atomic}
  \oneitem{Не знаю, используют ли их}
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Software Transactional Memory}
 Further reading:

 \link{http://research.microsoft.com/Users/simonpj/papers/stm/stm.pdf} - Composable Memory Transactions.
\end{frame}


\section{Производительность}

\begin{frame}
 \frametitle{Производительность}
 Что тормозит?
 \begin{itemize}
  \item Ждущие нити
  \item Захват (даже успешный) блокировок
  \item Переключение контекстов
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Производительность}
 Что делать?
 \begin{itemize}
  \item Не ждать и не блокироваться
  \item Не переключаться
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Уменьшение блокировок}
 Как не ждать?
 \begin{itemize}
  \item Использовать неблокирующие алгоритмы и операции
  \item Увеличить гранулярность блокировок
  \oneitem{Антоним: Один монитор на всю программу}
  \item Использовать алгоритмы, блокирующие не всех
  \oneitem{ReaderWriterLock}
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Неблокирующие алгоритмы и операции}
 Базис:
 \begin{itemize}
  \item \texttt{get}, \texttt{set}, \texttt{getAndSet}
  \item \texttt{boolean compareAndSet(expect, update)} (CAS)
  \begin{itemize}
   \item Поменять \emph{с expect} на update
   \item Если не expect - значит, мы прозевали, как кто-то поменял из другой нити
   \item Надо перезапустить кусок алгоритма в надежде, что теперь обойдется без коллизий
  \end{itemize}
  \item \texttt{addAndGet}, \texttt{getAndAdd}, \ldots
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Неблокирующие алгоритмы и операции}
 Средства в Java:
 \begin{itemize}
  \item \texttt{java.util.concurrent.atomic}
  \item \texttt{AtomicInteger}, \texttt{AtomicLong}
  \item \texttt{AtomicReference}, \texttt{AtomicStampedReference}
  \item (малоизвестно) \texttt{AtomicIntegerArray}, Long, Reference
 \end{itemize}
\end{frame}

\begin{frame}[fragile]
 \frametitle{Атомарные операции}
 Пример алгоритма на CAS:
 \begin{Verbatim}[fontsize=\tiny]
    public class ConcurrentStack<E> {
        AtomicReference<Node<E>> head = new AtomicReference<Node<E>>();

        public void push(E item) {
            Node<E> newHead = new Node<E>(item);
            Node<E> oldHead;
            do {
                oldHead = head.get();
                newHead.next = oldHead;
            } while (!head.compareAndSet(oldHead, newHead));
        }

        public E pop() {
            ...
        }
    }
 \end{Verbatim}
 \link{http://www.ibm.com/developerworks/java/library/j-jtp04186/index.html}
\end{frame}

\begin{frame}
 \frametitle{Неблокирующие контейнеры}
 Готовые неблокирующие структуры данных (New in JDK6):
 \begin{itemize}
  \item ConcurrentSkipListMap
  \item ConcurrentSkipListSet
 \end{itemize}
 Прелести:
 \begin{itemize}
  \item Итераторы никогда не бросают CME
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Уменьшение гранулярности блокировок}
 \begin{itemize}
  \item Блокируйте не всё
  \item Блокируйте не всех
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Уменьшение гранулярности блокировок}
 ``Блокируйте не всё'':

 Если надо защитить большую структуру данных, но меняются только ее куски - защищайте куски или группы кусков.

 Пример: \texttt{ConcurrentHashMap} (new in JDK6). Техника ``lock striping''.

 \begin{itemize}
  \item Чтение неблокирующее
  \item Запись блокирующая в $1/k$ случаев, где $k$ настраивается
  \oneitem{Рекомендуется $k \approx $ число нитей-писателей}
  \item $k$ блокировок защищают $k$ кусков хэш-таблицы
  \item Итераторы также не бросают CME
 \end{itemize}
\end{frame}


\begin{frame}
 \frametitle{Reader/Writer lock}
 ``Блокируйте не всех'':

 Чтение совместимо с чтением, но не с записью.

 Бывают разные:

 \begin{itemize}
  \item Readers-preference
  \item Writers-preference
  \item Arrival-order
  \item \ldots 
 \end{itemize}

 Класс \texttt{ReentrantReadWriteLock}. Реализует примерно arrival-order. Если есть ждущий писатель - новые читатели только после него.
\end{frame}

\begin{frame}
 \frametitle{Переключение контекстов}
 Как поменьше переключать контексты?
 \begin{itemize}
  \item Иметь поменьше нитей
  \oneitem{Например, одну (Event-driven)}
  \item Побольше асихронности
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Переключение контекстов}
 Как поменьше переключать контексты?

 Пусть нити не отвлекаются.
 \begin{itemize}
  \item Одни пихают задания в очередь
  \item Другие вынимают и исполняют их
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Цифры}
 Сколько реально стоят различные операции?
 \begin{tabular}{c|c}
  \hline
  Атомарные операции & $\approx$ 0.1мкс; incAndGet \\
  и volatile & 2-3x быстрее CAS \\
  Переключение контекста & Несколько мкс \\
                         & (независимо от числа нитей) \\
  Uncontended synchronized & $\approx$ 0.1-1мкс \\
  Contented synchronized & $\approx$ 20мкс \\
  \hline
 \end{tabular}

 \link{http://mailinator.blogspot.com/2008/03/how-fast-is-java-volatile-or-atomic-or.html} - сравнение скорости различных способов синхронизации
\end{frame}

\begin{frame}
 \frametitle{Что умеет JVM?}
 \begin{itemize}
  \item Biased locking
  \item Lock coarsening
  \item Lock elision (escape analysis)
 \end{itemize}

 \link{http://www.infoq.com/articles/java-threading-optimizations-p1} - Do Java threading optimizations actually work?
\end{frame}

\begin{frame}
 \frametitle{Что умеет JVM?}
 Biased locking (new in 1.5.0\_6):
 \begin{itemize}
  \item Большинство объектов за всю жизнь блокирует только 1 нить
  \item Делается так, чтобы для этой нити синхронизация была \emph{очень} быстрой (даже без CAS)
  \item \texttt{-XX:+UseBiasedLocking} (по умолчанию включено начиная с Java SE 6)
 \end{itemize}

 \link{http://tinyurl.com/biasedlocking} - от разработчиков JVM, по-русски
\end{frame}

\begin{frame}[fragile]
 \frametitle{Что умеет JVM?}
 Lock coarsening:
 \begin{Verbatim}[fontsize=\tiny]
  public void setupFoo(Foo foo) {
      foo.setBarCount(1);
      foo.setQuxEnabled(true);
      foo.addGazonk(new Gazonk());
  }
 \end{Verbatim}
 \ldots и все 3 метода \texttt{synchronized}.

 Тут незачем делать \texttt{synchronized} 3 раза. Можно запихнуть все в 1 \texttt{synchronized}.

 Опция \texttt{-XX:+EliminateLocks} (по умолчанию включено).

 \link{http://citeseer.ist.psu.edu/459328.html} - статья про технику.

\end{frame}

\begin{frame}[fragile]
 \frametitle{Что умеет JVM?}
 Escape analysis: Если объект не убегает в другую нить, то нет смысла делать на нем \texttt{synchronized}.

 \begin{Verbatim}[fontsize=\tiny]
  DeepThought dt = new DeepThought();
  dt.turnOnPower();
  dt.enterData(data);
  dt.wakeup();
  return dt.computeUltimateAnswer();
 \end{Verbatim}

 Опция \texttt{-XX:+DoEscapeAnalysis}.
\end{frame}

\section{На закуску}

\begin{frame}
 \frametitle{Cutting edge}
 Что умеет Haskell:
 \begin{itemize}
  \item Все побочные эффекты контролируются
  \item Нет неконтролируемых проблем из-за их наличия
  \item Позволяет немыслимые в других языках вещи
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Cutting edge}
 Что умеет Haskell:
 \begin{itemize}
  \item Самые быстрые в мире легковесные нити и примитивы синхронизации
  \oneitem{1 место на Language Shootout, 60x быстрее нативных Ubuntu, 5х быстрее Erlang!}
  \item Параллельные стратегии
  \oneitem{Простые \emph{параллельные} вычисления: нет аналогов в других языках}
  \item Data Parallel Haskell
  \oneitem{Автоматически распараллеливаемые векторные вычисления}
  \item Транзакционная память
  \item Работа в направлении GPU
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Легковесные нити}
 Nothing special, просто очень быстрые и почти 0 синтаксического оверхеда.

 C++0x futures/promises and more в 60 строк.
\end{frame}

\begin{frame}[fragile]
 \frametitle{Параллельные стратегии}
 Ленивость позволяет отделить алгоритм и способ распараллеливания.

 Примитив \texttt{par}: \texttt{x `par` y} - параллельно вычислить x, y.

 \begin{Verbatim}
  results = map f args `using` parList rnf

  -- | Applies a strategy to every
  -- element of a list in parallel.
  parList :: Strategy a -> Strategy [a]
  parList st []     = ()
  parList st (x:xs) = st x `par` (parList st xs)
 \end{Verbatim}

 Идея - ядерная. Это можно реализовать и на Java, если постараться. 
\end{frame}

\begin{frame}[fragile]
 \frametitle{Data Parallel Haskell}

 \begin{itemize}
  \item Векторизатор (транслирует даже рекурсивные функции в векторные операции)
  \item Библиотека параллельных векторных операций
 \end{itemize}

 \begin{Verbatim}
  dotp_double :: [:Double:] -> [:Double:] -> Double
  dotp_double xs ys = sumP [:x * y | x <- xs | y <- ys:]

  smMul :: [:[:(Int,Float):]:] -> [:Float:] -> Float
  smMul sm v = sumP [: svMul sv v | sv <- sm :]
 \end{Verbatim}

 \url{http://research.microsoft.com/en-us/um/people/simonpj/papers/ndp/NdpSlides.pdf} - слайды
\end{frame}

\begin{frame}[fragile]
 \frametitle{Data Parallel Haskell}
 \begin{Verbatim}
  sort :: [:Float:] -> [:Float:]
  sort a = if (length a <= 1) then a
         else sa!0 +++ eq +++ sa!1
   where
      m = a!0
      lt = [: f | f<-a, f<m :]
      eq = [: f | f<-a, f==m :]
      gr = [: f | f<-a, f>m :]
      sa = [: sort a | a <- [:lt,gr:] :]
 \end{Verbatim}
 Векторизуется и параллелизуется.
\end{frame}

\begin{frame}[fragile]
 \frametitle{Транзакционная память}
 \begin{Verbatim}
    transfer :: Account -> Account -> Int -> IO ()
    transfer from to amount = atomically $ do 
      deposit  to   amount
      withdraw from amount
  \end{Verbatim}
\end{frame}

\begin{frame}[fragile]
 \frametitle{Транзакционная память}
 \begin{Verbatim}
  check True = return ()
  check False = retry

  limitedWithdraw :: Account -> Int -> STM ()
  limitedWithdraw acc amount = do
      bal <- readTVar acc
      check (amount <= 0 || amount <= bal)
      writeTVar acc (bal - amount)
 \end{Verbatim}

 Четкое разделение между:
 \begin{itemize}
  \item IO - код с произвольными побочными эффектами
  \item STM - код, единственный эффект которого - работа с транзакционной памятью
  \item \texttt{atomically :: STM t -> IO t}
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Что было}
 \begin{itemize}
  \item Классификация многопоточных программ
  \item Формальные методы (LTL) и тулы (SPIN,JPF,CheckThread)
  \item Java memory model
  \item Корректность: инкапсуляция состояния, дедлоки, атомарные и идемпотентные операции
  \item Тестирование: Фазы (последовательная работа, корректная работа, устойчивость к нагрузке), повторяемость, тулы
  \item Методики: fork/join, векторные алгоритмы, message-passing, event-driven, STM
  \item Производительность: влияющие факторы, гранулярность блокировок, цифры и конкретика JVM
  \item Haskell: легкие нити, параллельные стратегии, векторизация, STM
 \end{itemize}

\end{frame}

\begin{frame}
 \frametitle{The end}
 \begin{center}Спасибо! Вопросы?\end{center}
\end{frame}


\end{document}