\documentclass[pdftex,a4,11pt]{seminar}
% Definition of packages to use...........................................
% (all in standard LaTeX distribution)

% Identification of the file................................................
\def\FileAuthor{Helge Jensen}
\def\FileTitle{Concurrency and Locking in C\#}
\input{concurrency_and_locking.svn.tex}
\def\FileSubject{\docsvnurl}

\newcommand{\pdftitle}{Exceptions and Using in Csharp}
\newcommand{\pdfsubject}{\FileSubject{}}
\newcommand{\pdfkeywords}{Csharp, Programming, Idiom, lock, WaitHandle}
\newcommand{\pdfauthor}{Helge Jensen}

\input{head.tex}

\begin{document}
 \raggedright
 \pagestyle{fancy}

 \begin{slide}
  \begin{center}
    {\color{title}\bf \Huge \FileTitle{}}\\
    \vspace{1ex}
    {\large\textit{\FileAuthor{}}}\\
    {\scriptsize\url{\docsvnurl/}}\\
    \fbox{
    \begin{minipage}{.7\textwidth}
      \ptsize{8}
      \VerbatimInput[fontsize=\tiny]{.svninfo}
      \VerbatimInput[fontsize=\tiny]{.svnstatus}
    \end{minipage}}
  \end{center}
 \end{slide}

 \begin{slide}
   \slideheading{The Account example}
\begin{CS}
class Account {
  protected int balance; 
  ...
  void Deposit(int amount) { balance += amount; }
}
\end{CS}
   \begin{itemize}
     \item What's ``wrong'' with this code?
     \item What if 2 deposits are done at the same time
     \item Atomic updates required
   \end{itemize}
 \end{slide}

 \begin{slide}
   \slideheading{Solutions}
   \begin{itemize}
     \item Critical Regions
     \item Mutual Exclusion (Mutex, \cscode{ManualResetEvent})
     \item Recursive Locks (\cscode{lock})
     \item Atomic Swap     (\cscode{Interlocked.Exchange})
     \item Conditioned Atomic Swap (\cscode{Interlocked.CompareExchange})
   \end{itemize}
   The solutions are all computationally equivalent (you can build all
   from any)
 \end{slide}

 \begin{slide}
   \slideheading{Critical Regions}
   \begin{itemize}
       \item One solution: ``lock'' all updating of data that depends on timing
       \item Dijkstra: Critical region, a piece of code which only one
       execution path can execute at a time
\begin{CS}
class Account {
  protected int balance; 
  ...
  void Deposit(int amount) { 
    CriticalRegion { // Not C#
      balance += amount;
    }
  }
}
\end{CS}
       \item One problem: all updates that interdepend must be in same
       critical region
     \end{itemize}
 \end{slide}

 \begin{slide}
 \slideheading{Mutual Exclusion}
 \begin{itemize}
   \item Mut(ual)ex(clusion), well known implemented almost everywhere
   \item Extracting the critical region from source location
   \item Either ``locked'' or ``unlocked''.
   \item Operations:
\begin{CS}
    // Waits for state ``unlocked'',
    // only 1 caller allowed to continue
    void Lock(); 
    // Changes state from ``locked'' to ``unlocked''
    void Unlock();
    // Allows non-blocking acquisition of lock
    void bool TryLock();
\end{CS}
\clearpage
   \item Account with Mutex
\begin{CS}
class Account {
  protected int balance; 
  protected Mutex mutex;
  ...
  void Deposit(int amount) { 
    mutex.Lock();
    try {
      balance += amount;
    } finally {
      mutex.Unlock();
    }
  }
}
\end{CS}
   \item More flexible than Critical Region
   \item Error-prone: fogot \cscode{Unlock()}, esp. in presence of
   exceptions
 \end{itemize}
 \end{slide}

 \begin{slide}
   \slideheading{Mutex in .NET/C\#}
   \begin{itemize}
     \item Implemented with \cscode{ManualResetEvent}:
\begin{CS}
class Account {
  protected int balance; 
  protected ManualResetEvent mutex = new ManalResetEvent;
  ...
  void Deposit(int amount) {
    mutex.WaitOne(); // Lock()
    try {
      balance += amount;
    } finally {
      mutex.Reset(); // Unlock()
    }
  }
}
\end{CS}
   \end{itemize}
 \end{slide}

 \begin{slide}
   \slideheading{Recursive Lock}
   \begin{itemize}
     \item Let the same thread of execution do \cscode{Lock()} any number of times
     \item Require the same number of \cscode{Unlock()}
     \item Supported with C\# keyword: \cscode{lock (object)}
   \item Account with \cscode{lock}
\begin{CS}
class Account {
  protected int balance; 
  ...
  void Deposit(int amount) { 
    lock (this) {
      balance += amount;
    }
  }
}
\end{CS}
    \item \cscode{lock} can only follow scope, but remembers unlock
   \end{itemize}
 \end{slide}

 \begin{slide}
   \slideheading{Atomic Swap}
   \begin{itemize}
     \item An ``optimistic'' strategy: doesn't allow you to work consistently
     \item Allows you to \emph{detect} inconsistencies
     \item Account with Atomic Swap
\begin{CS}
class Account {
  protected int balance; 
  ...
  void Deposit(int amount) { 
    int before = balance;
    int during = Interlocked.Exchange(ref balance, balance + amount);
    if ( before != during )
      throw new Exception("Invalid account update!");
  }
}
\end{CS}
     \item Why does it exists?
       \begin{itemize}
         \item Can be implemented VERY efficiently, is a CPU instruction
       \end{itemize}
   \end{itemize}
 \end{slide}

 \begin{slide}
   \slideheading{Conditioned Atomic Swap}
   \begin{itemize}
     \item Compromise between Mutex and Swap, 
       Does Atomic Swap, but only if it value to swap with is known
     \item Account with Conditioned Atomic Swap
\begin{CS}
class Account {
  protected int balance;
  void Deposit(int amount) { 
    while ( true ) {
      int before = balance;
      int after = balance + amount;
      if ( Interlocked.CompareExchange(ref balance, after, before) == after )
        return;      
    }
  }
}
\end{CS}
   \item Can be implemented VERY efficiently, Is consistent, Is CPU instruction
   \end{itemize}
 \end{slide}

 \begin{slide}
   \slideheading{Concurrency}
   \begin{itemize}
     \item Processes: no memory sharing
     \item Threads: shares everything but execution-path and stack
     \item \cscode{new Thread(ThreadStart)}
     \item Async Delegate: run delegate async
     \item \cscode{BeginInvoke(...)}, \cscode{EndInvoke(IAsyncResult)}
   \end{itemize}
 \end{slide}

 \begin{slide}
   \slideheading{Exceptions and Concurrency}
   \begin{itemize}
     \item Being on the top of the stack makes you extra responsible
     \item Default behaviour on uncaught exceptions: terminate and ignore
     \item Preferred (generic) behaviour:
       \begin{CS}
void ToRunAsync(...) {
  try {
    // do stuff
  } catch ( Exception e ) {
    Log.log(e);
    throw; // rethrow to terminate thread in the default way
  }
} 
       \end{CS}
   \end{itemize}
 \end{slide}

 \begin{slide}
   \slideheading{Thread}
   \begin{itemize}
     \item A seperate execution-path in the program
     \item Shares data with other threads, except stack
   \end{itemize}
   \begin{CS}
delegate void ThreadStart(void);
class Thread {
  public Thread(ThreadStart); // Allocate a new thread
  public Start();             // Begin execution
  // less used
  public Join();              // Wait for termination
  public Abort();             // Throw Exception in thread
  public Suspend();           // Suspend execution
  public Resume();            // Resume execution
}    
   \end{CS}
 \end{slide}

 \begin{slide}
   \begin{CS}
class EchoService {
  TcpListener l;
  public EchoService(TcpListener l) { this.l = l; };
  public Serve() {
    while ( true ) {
      NetworkStream s = l.AcceptTcpClient().GetStream();
      new Thread(new ThreadStart(new Handler(s).handle)).Start();
    }
  }
}
class Handler {
  Stream s;
  public Handler(Stream s) { this.s = s; }
  void Handle() {
    byte[] buf = new byte[100];
    for(int r = -1; r != 0; ) {
      r = s.Read(buf,0,buf.Length()); s.Write(buf,0,r);
    }
  }
}     
   \end{CS}
 \end{slide}

 \begin{slide}
   \slideheading{Thread properties}
   \begin{itemize}
     \item Limited amount of threads: ~2000
     \item Fire-and-forget: no cleanup needed
     \item No arguments, must have state in delegates instance
     \item \emph{Requires thought for exceptions}
   \end{itemize}
 \end{slide}

 \begin{slide}
   \slideheading{\texttt{BeginInvoke(...),EndInvoke(IAsyncResult)}}
   \begin{itemize}
     \item Generated for the compiler for all delegates
     \item Starts execution of a delegate in separate execution path
     \item Example:
\begin{CS}
  delegate void Foo(int x, Object y, Bar bar);
\end{CS}
     \item Yields \cscode{Foo.BeginInvoke(...)} with signature:
\begin{CS}
  IAsyncResult BeginInvoke(int x, Object y, Bar bar, 
                           AsyncCallback callback,
                           Object state);
\end{CS}
     \item Callback gets invoked with the IAsyncResult after termination
     \item You \emph{must} call \cscode{EndInvoke} on returned result
       at some point, AFTER the async exection terminate.
     \item Usually the callback will call EndInvoke
   \end{itemize}
 \end{slide}

 \begin{slide}
   \slideheading{The callback}
   \begin{itemize}
     \item interface:
   \begin{CS}
 delegate void AsyncCallback(IAsyncResult r);
   \end{CS}
     \item gets invoked when the async invocation ends
     \item gets called on the returned IAsyncResult
     \item is usefull for invoking \cscode{EndInvoke}
       \begin{CS}
void RunAsync() {
  Foo foo = new Foo(someMethod);
  foo.BeginInvoke(arg1, arg2, ..., new AsyncCallback(Cleanup), foo);
}
void Cleanup(IAsyncResult asyncResult) {
  Foo foo = (Foo)asyncResult.AsyncState;
  foo.EndInvoke(asyncResult);
}
       \end{CS}
   \end{itemize}
 \end{slide}

 \begin{slide}
   \slideheading{IAsyncResult}
   \begin{itemize}
     \item Represent an ongoing, possibly already completed call.
     \item Interface:
       \begin{CS}
interface IAsyncResult {
  Object AsyncState;          // state passed to BeginInvoke
  WaitHandle AsyncWaitHandle; // WaitHandle for completion
  bool IsCompleted;           // Done?
}
       \end{CS}
     \item Waiting for completion:
 \begin{CS}
   Foo foo = new Foo(f);
   IAsyncResult r = foo.BeginInvoke(1, null, new Bar(), FooEnd, foo);
   ...
   r.AsyncWaitHandle.WaitOne(); // wait for completion
 \end{CS}
   \end{itemize}
 \end{slide}


 \begin{slide}
   \begin{CS}
class EchoService {
  delegate void Handler(Stream s);
  public void Handle(Stream s) {
    byte[] buf = new byte[100];
    for(int r = -1; r != 0; ) {
      r = s.Read(buf,0,buf.Length()); s.Write(buf,0,r);
    }
  }
  public void EndHandle(IAsyncResult asyncResult) {
    Handler h = (Handler)(asyncResult.AsyncState);
    h.EndInvoke(asyncResult);
  }
  public Serve() {
    while ( true ) {
      NetworkStream s = l.AcceptTcpClient().GetStream();
      Handler h = new Handler(Handle);
      h.BeginInvoke(s, EndHandle, h);
    }
  }
}
   \end{CS}
 \end{slide}

 \begin{slide}
     \slideheading{Async delegate properties}
     \begin{itemize}
       \item Complicated, requires EndInvoke
       \item Not limited to thread count
       \item Runs in a thread-pool, so it \emph{may} block. In later
       implementations of .NET this \emph{may} be improved.
       \item Offers good performance
       \item Resembles the async I/O interface
     \end{itemize}
 \end{slide}

 \begin{slide}
   \slideheading{Warning: Timers}
     \begin{CS}
void Deposit(Object state) { balance += (int)state; }
void PayPerSecond() {
  using ( Timer t = new Timer(
                      new TimerCallback(Deposit),
                      10, // state for callback
                      TimeSpan.FromSeconds(0.0),// start now
                      TimeSpan.FromSeconds(1.0) // every second
                      ) )
    while (balance < 100)
      Thread.Sleep(TimeSpan.FromSeconds(1.0));
}
     \end{CS}
     \begin{itemize}
       \item If \cscode{Deposit} takes longer than 1.0 seconds, we
       need to synchronize
       \item This happens in the real world
     \end{itemize}
 \end{slide}

 \begin{slide}
   \slideheading{Warning: conditioned update}
   \begin{CS}
void Deposit(int amount) {
  // Accounts can hold max 100
  if ( balance + amount > 100 )
    throw new FilthyRichException(this);
  else
    balance += amount;
}
   \end{CS}
   \begin{itemize}
     \item What's wrong here?
     \item Use 2 execution-paths to show that \cscode{balance > 100} can occur
     \item Hint: balance may change after checking condition
   \end{itemize}
 \end{slide}

 \begin{slide}
   \slideheading{Thread-safety}
   \begin{itemize}
     \item What does ``thread-safe'' mean? What is it \emph{safe} for?
     \item Thread-safe usually means: ``Will consistently fail to work if not synchronized properly''
     \item Example: Collections in .NET have Synchronized wrappers
       \begin{CS}
class UserDatabase {
  IDictionary users = Hashtable.Synchronized(new Hashtable());
  void Add(string name, object info) {
    if ( users.Contains(name) )
      throw new UsernameTaken(name, this);
    else
      dict[name] = info;
  }
}
       \end{CS}
     \item Suffers from ``conditioned update'' problem!
     \item Rewrite to work properly
   \end{itemize}
 \end{slide}

 \begin{slide}
   \slideheading{Simple Solution}
       \begin{CS}
class UserDatabase {
  IDictionary users = new Hashtable();
  void Add(string name, object info) {
    lock ( users.SyncRoot )
      if ( users.Contains(name) )
        throw new UsernameTaken(name, this);
      else
        dict[name] = info;
  }
}
       \end{CS}
       \begin{itemize}
         \item Can you do it more efficiently?
       \end{itemize}
 \end{slide}
 \begin{slide}
   \slideheading{Possibly more efficient solution}
       \begin{CS}
class UserDatabase {
  IDictionary users = new Hashtable();
  void Add(string name, object info) {
    if ( users.Contains(name) )
      throw new UsernameTaken(name, this);
    else
      lock ( users.SyncRoot )
        if ( users.Contains(name) )
          throw new UsernameTaken(name, this);
        else
          dict[name] = info;
  }
}
       \end{CS}
 \end{slide}

 \begin{slide}
   \slideheading{Conclusion}
   \begin{itemize}
     \item Consider what needs protection
       \begin{itemize}
         \item Don't ``overprotect'', it's OK to demand caller to do
         synchronization
         \item Don't ``underprotect'', esp. for nonatomic state-update
         in caches
         \item Watch out for ``usual suspects''
       \end{itemize}
     \item Select the proper protection
       \begin{itemize}
         \item scoped: lock
         \item distributed: Mutex,
         \item performance \emph{critical}: consider Atomic Swaps
       \end{itemize}
     \item Select the proper concurrency
       \begin{itemize}
         \item Amount of simultaneous execution
       \end{itemize}
     \item \emph{Watch out for exceptions}
       \begin{itemize}
         \item Default action for uncatched exceptions is terminate
         without telling anyone.
       \end{itemize}
   \end{itemize}
 \end{slide}

\end{document}