1[/
2 / Copyright (c) 2008,2014 Vicente J. Botet Escriba
3 /
4 / Distributed under the Boost Software License, Version 1.0. (See accompanying
5 / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 /]
7
8
9[section  Internal Locking]
10[note This tutorial is an adaptation of chapter Concurrency of the Object-Oriented Programming in the BETA Programming Language and  of the paper of Andrei Alexandrescu "Multithreading and the C++ Type System" to the Boost library.]
11[section Concurrent threads of execution]
12
13Consider, for example, modeling a bank account class that supports simultaneous deposits and withdrawals from multiple locations (arguably the "Hello, World" of multithreaded programming).
14
15From here a component is a model of the `Callable` concept.
16
17I C++11 (Boost) concurrent execution of a component is obtained by means of the `std::thread`(`boost::thread`):
18
19    boost::thread thread1(S);
20
21where `S` is a model of `Callable`. The meaning of this expression is that execution of `S()` will take place concurrently with the current thread of execution executing the expression.
22
23The following example includes a bank account of a person (Joe) and two components, one corresponding to a bank agent depositing money in Joe's account, and one representing Joe. Joe will only be withdrawing money from the account:
24
25  class BankAccount;
26
27  BankAccount JoesAccount;
28
29  void bankAgent()
30  {
31      for (int i =10; i>0; --i) {
32          //...
33          JoesAccount.Deposit(500);
34          //...
35      }
36  }
37
38  void Joe() {
39      for (int i =10; i>0; --i) {
40          //...
41          int myPocket = JoesAccount.Withdraw(100);
42          std::cout << myPocket << std::endl;
43          //...
44      }
45  }
46
47  int main() {
48      //...
49      boost::thread thread1(bankAgent); // start concurrent execution of bankAgent
50      boost::thread thread2(Joe); // start concurrent execution of Joe
51      thread1.join();
52      thread2.join();
53      return 0;
54  }
55
56From time to time, the `bankAgent` will deposit $500 in `JoesAccount`. `Joe` will similarly withdraw $100 from his account. These sentences describe that the `bankAgent` and `Joe` are executed concurrently.
57
58[endsect]
59[section  Internal locking]
60
61The above example works well as long as the components `bankAgent` and `Joe` doesn't access `JoesAccount` at the same time. There is, however, no guarantee that this will not happen. We may use a mutex to guarantee exclusive access to each bank.
62
63  class BankAccount {
64      boost::mutex mtx_;
65      int balance_;
66  public:
67      void Deposit(int amount) {
68          mtx_.lock();
69          balance_ += amount;
70          mtx_.unlock();
71      }
72      void Withdraw(int amount) {
73          mtx_.lock();
74          balance_ -= amount;
75          mtx_.unlock();
76      }
77      int GetBalance() {
78          mtx_.lock();
79          int b = balance_;
80          mtx_.unlock();
81          return b;
82      }
83  };
84
85Execution of the `Deposit` and `Withdraw` operations will no longer be able to make simultaneous access to balance.
86
87A mutex is a simple and basic mechanism for obtaining synchronization. In the above example it is relatively easy to be convinced that the synchronization works correctly (in the absence of exception). In a system with several concurrent objects and several shared objects, it may be difficult to describe synchronization by means of mutexes. Programs that make heavy use of mutexes may be difficult to read and write. Instead, we shall introduce a number of generic classes for handling more complicated forms of synchronization and communication.
88
89With the RAII idiom we can simplify a lot this using the scoped locks. In the code below, guard's constructor locks the passed-in object `mtx_`, and guard's destructor unlocks `mtx_`.
90
91  class BankAccount {
92      boost::mutex mtx_; // explicit mutex declaration
93      int balance_;
94  public:
95      void Deposit(int amount) {
96          boost::lock_guard<boost::mutex> guard(mtx_);
97          balance_ += amount;
98      }
99      void Withdraw(int amount) {
100          boost::lock_guard<boost::mutex> guard(mtx_);
101          balance_ -= amount;
102      }
103      int GetBalance() {
104          boost::lock_guard<boost::mutex> guard(mtx_);
105          return balance_;
106      }
107  };
108
109The object-level locking idiom doesn't cover the entire richness of a threading model. For example, the model above is quite deadlock-prone when you try to coordinate multi-object transactions. Nonetheless, object-level locking is useful in many cases, and in combination with other mechanisms can provide a satisfactory solution to many threaded access problems in object-oriented programs.
110
111[endsect]
112[section  Internal and external locking]
113
114The BankAccount class above uses internal locking. Basically, a class that uses internal locking guarantees that any concurrent calls to its public member functions don't corrupt an instance of that class. This is typically ensured by having each public member function acquire a lock on the object upon entry. This way, for any given object of that class, there can be only one member function call active at any moment, so the operations are nicely serialized.
115
116This approach is reasonably easy to implement and has an attractive simplicity. Unfortunately, "simple" might sometimes morph into "simplistic."
117
118Internal locking is insufficient for many real-world synchronization tasks. Imagine that you want to implement an ATM withdrawal transaction with the BankAccount class. The requirements are simple. The ATM transaction consists of two withdrawals-one for the actual money and one for the $2 commission. The two withdrawals must appear in strict sequence; that is, no other transaction can exist between them.
119
120The obvious implementation is erratic:
121
122  void ATMWithdrawal(BankAccount& acct, int sum) {
123      acct.Withdraw(sum);
124      // preemption possible
125      acct.Withdraw(2);
126  }
127
128The problem is that between the two calls above, another thread can perform another operation on the account, thus breaking the second design requirement.
129
130In an attempt to solve this problem, let's lock the account from the outside during the two operations:
131
132  void ATMWithdrawal(BankAccount& acct, int sum) {
133      boost::lock_guard<boost::mutex> guard(acct.mtx_); 1
134      acct.Withdraw(sum);
135      acct.Withdraw(2);
136  }
137
138Notice that the code above doesn't compile, the `mtx_` field is private.
139We have two possibilities:
140
141* make `mtx_` public which seems odd
142* make the `BankAccount` lockable by adding the lock/unlock functions
143
144We can add these functions explicitly
145
146  class BankAccount {
147      boost::mutex mtx_;
148      int balance_;
149  public:
150      void Deposit(int amount) {
151          boost::lock_guard<boost::mutex> guard(mtx_);
152          balance_ += amount;
153      }
154      void Withdraw(int amount) {
155          boost::lock_guard<boost::mutex> guard(mtx_);
156          balance_ -= amount;
157      }
158      void lock() {
159          mtx_.lock();
160      }
161      void unlock() {
162          mtx_.unlock();
163      }
164  };
165
166or inheriting from a class which add these lockable functions.
167
168The `basic_lockable_adapter` class helps to define the `BankAccount` class as
169
170  class BankAccount
171  : public basic_lockable_adapter<mutex>
172  {
173      int balance_;
174  public:
175      void Deposit(int amount) {
176          boost::lock_guard<BankAccount> guard(*this);
177          balance_ += amount;
178      }
179      void Withdraw(int amount) {
180          boost::lock_guard<BankAccount> guard(*this);
181          balance_ -= amount;
182      }
183      int GetBalance() {
184          boost::lock_guard<BankAccount> guard(*this);
185          return balance_;
186      }
187  };
188
189
190and the code that doesn't compiles becomes
191
192  void ATMWithdrawal(BankAccount& acct, int sum) {
193      boost::lock_guard<BankAccount> guard(acct);
194      acct.Withdraw(sum);
195      acct.Withdraw(2);
196  }
197
198Notice that now acct is being locked by Withdraw after it has already been locked by guard. When running such code, one of two things happens.
199
200* Your mutex implementation might support the so-called recursive mutex semantics. This means that the same thread can lock the same mutex several times successfully. In this case, the implementation works but has a performance overhead due to unnecessary locking. (The locking/unlocking sequence in the two Withdraw calls is not needed but performed anyway-and that costs time.)
201* Your mutex implementation might not support recursive locking, which means that as soon as you try to acquire it the second time, it blocks-so the ATMWithdrawal function enters the dreaded deadlock.
202
203As `boost::mutex` is not recursive, we need to use its recursive version `boost::recursive_mutex`.
204
205  class BankAccount
206  : public basic_lockable_adapter<recursive_mutex>
207  {
208
209      // ...
210  };
211
212The caller-ensured locking approach is more flexible and the most efficient, but very dangerous. In an implementation using caller-ensured locking, BankAccount still holds a mutex, but its member functions don't manipulate it at all. Deposit and Withdraw are not thread-safe anymore. Instead, the client code is responsible for locking BankAccount properly.
213
214    class BankAccount
215        : public basic_lockable_adapter<boost:mutex> {
216        int balance_;
217    public:
218        void Deposit(int amount) {
219            balance_ += amount;
220        }
221        void Withdraw(int amount) {
222            balance_ -= amount;
223        }
224    };
225
226Obviously, the caller-ensured locking approach has a safety problem. BankAccount's implementation code is finite, and easy to reach and maintain, but there's an unbounded amount of client code that manipulates BankAccount objects. In designing applications, it's important to differentiate between requirements imposed on bounded code and unbounded code. If your class makes undue requirements on unbounded code, that's usually a sign that encapsulation is out the window.
227
228To conclude, if in designing a multi-threaded class you settle on internal locking, you expose yourself to inefficiency or deadlocks. On the other hand, if you rely on caller-provided locking, you make your class error-prone and difficult to use. Finally, external locking completely avoids the issue by leaving it all to the client code.
229
230
231[endsect]
232
233[/
234[section  Monitors]
235
236The use of `mutex` and `lockers`, as in `BankAccount`, is a common way of defining objects shared by two or more concurrent components. The basic_lockable_adapter class was a first step.
237We shall therefore introduce an abstraction that makes it easier to define such objects.
238The following class describes a so-called monitor pattern.
239
240  template <
241      typename Lockable=mutex
242  >
243  class basic_monitor : protected basic_lockable_adapter<Lockable> { // behaves like a BasicLockable for the derived classes
244  protected:
245      typedef unspecified synchronizer; // is a strict lock guard
246  };
247
248[/shared_monitor]
249[/monitor]
250
251A basic_monitor object behaves like a `BasicLockable` object but only for the inheriting classes.
252Protected inheritance from lockable_adapter provide to all the derived classes all BasicLockable operations. In addition has a protected nested class, synchronizer, used when defining the monitor operations to synchronize the access critical regions. The BankAccount may be described using Monitor in the following way:
253
254  class BankAccount : protected basic_monitor<>
255  {
256  protected:
257      int balance_;
258  public:
259      BankAccount() : balance_(0) {}
260      BankAccount(const BankAccount &rhs) {
261          synchronizer _(*rhs.mutex());
262          balance_=rhs.balance_;
263      }
264
265      BankAccount& operator=(BankAccount &rhs)
266      {
267          if(&rhs == this) return *this;
268
269          int balance=0;
270          {
271              synchronizer _(*rhs.mutex());
272              balance=rhs.balance_;
273          }
274          synchronizer _(*this->mutex());
275          balance_=balance;
276          return *this;
277      }
278
279      void Deposit(int amount) {
280          synchronizer _(*this->mutex());
281          balance_ += amount;
282      }
283      int Withdraw(int amount) {
284          synchronizer _(*this->mutex());
285          balance_ -= amount;
286          return amount;
287      }
288      int GetBalance() {
289          synchronizer _(*this->mutex());
290          return balance_;
291      }
292  };
293
294In the following, a monitor means some sub-class of monitor. A synchronized operation means an operation using the synchronizer guard defined within some monitor. Monitor is one example of a high-level concurrency abstraction that can be defined by means of mutexes.
295
296
297[section Monitor Conditions]
298
299It may happen that a component executing an entry operation of a monitor is unable to continue execution due to some condition not being fulfilled. Consider, for instance, a bounded buffer of characters. Such a buffer may be implemented as a monitor with two operations Push and Pull: the Puss operation cannot be executed if the buffer is full, and the Pull operation cannot be executed if the buffer is empty. A sketch of such a buffer monitor may look as
300follows:
301
302  class sync_buffer {
303      boost::mutex mtx_; 1
304  public:
305      ...
306      bool full() { return in_==out_; }
307      bool empty() { return in_==(out_%size)+1; }
308      void push(T& v) {
309          // wait if buffer is full
310          data_[in_]=v;
311          in_ = (in_% size)+1;
312      }
313      T pull() {
314          // wait if buffer is empty
315          out_ = (out_% size)+1;
316          return data_[out_];
317      }
318  };
319
320The meaning of a wait is that the calling component is delayed until the condition becomes true. We can do that using Boost.Thread condition variables like:
321
322  template <typename T, unsigned size>
323  class sync_buffer
324  {
325      typedef boost::mutex mutex_type;
326      typedef boost::condition_variable condition_type;
327      typedef boost::unique_lock<mutex_type> unique_lock_type;
328      mutex_type mtx_;
329      condition_type not_full_;
330      condition_type not_empty_;
331
332      T data_[size+1];
333      unsigned in_, out_;
334
335  public:
336      sync_buffer():in_(0), out_(0) {}
337
338      bool full() { return out_==(in_+1)%(size+1); }
339      bool empty() { return out_==in_; }
340
341      unsigned get_in() {return in_;}
342      unsigned get_out() {return out_;}
343      void push(T v) {
344          unique_lock_type guard(mtx_); 1
345          while (full()) { 2
346              not_full_.wait(guard);
347          }
348          data_[in_]=v;
349          in_ = (in_+1)% (size+1);
350          not_empty_.notify_one(); 3
351      }
352
353      T pull() {
354          unique_lock_type guard(mtx_); 4
355          while (empty()) { 5
356              not_empty_.wait(guard);
357          }
358          unsigned idx = out_;
359          out_ = (out_+1)% (size+1);
360          not_full_.notify_one(); 6
361          return data_[idx];
362      }
363  };
364
365The Monitor class replace the nested synchronizer unique_lock with the class `condition_unique_lock` for this purpose:
366
367  template <
368      typename Lockable,
369      class Condition=condition_safe<typename best_condition<Lockable>::type >
370      , typename ScopeTag=typename scope_tag<Lockable>::type
371  >
372  class condition_unique_lock
373      : protected unique_lock<Lockable,ScopeTag>
374  {
375      BOOST_CONCEPT_ASSERT((LockableConcept<Lockable>));
376  public:
377      typedef Lockable lockable_type;
378      typedef Condition condition;
379
380      explicit condition_unique_lock(lockable_type& obj); 1
381      condition_unique_lock(lockable_type& obj, condition &cond); 2
382      template <typename Predicate>
383      condition_unique_lock(lockable_type& obj, condition &cond, Predicate pred); 3
384      ~condition_unique_lock() 4
385
386      typedef bool (condition_unique_lock::*bool_type)() const; 5
387      operator bool_type() const; 6
388      bool operator!() const { return false; } 7
389      bool owns_lock() const { return true; } 8
390      bool is_locking(lockable_type* l) const 9
391
392      void relock_on(condition & cond);
393      template<typename Clock, typename Duration>
394      void relock_until(condition & cond, chrono::time_point<Clock, Duration> const& abs_time);
395      template<typename duration_type>
396      void relock_on_for(condition & cond, duration_type const& rel_time);
397
398      template<typename Predicate>
399      void relock_when(condition &cond, Predicate pred);
400      template<typename Predicate>
401      template<typename Clock, typename Duration>
402      void relock_when_until(condition &cond, Predicate pred,
403              chrono::time_point<Clock, Duration> const& abs_time);
404      template<typename Predicate, typename duration_type>
405      void relock_when_for(condition &cond, Predicate pred,
406              duration_type const& rel_time);
407
408      10
409  };
410
411
412We may now give the complete version of the buffer class. The content of the buffer is: `data_[out_+1], data_[out_+2], ... data_R[in_-1]` where all the indexes are modulo size. The buffer is full if `in_=out_` and it is empty if `in_=(out_+1)%size`.
413
414  template <typename T, unsigned size>
415  class sync_buffer : protected basic_monitor<>
416  {
417      condition not_full_;
418      condition not_empty_;
419
420      T data_[size+1];
421      unsigned in_, out_;
422
423      struct  not_full {
424          explicit not_full(sync_buffer &b):that_(b){};
425          bool operator()() const { return !that_.full(); }
426          sync_buffer &that_;
427      };
428      struct  not_empty {
429          explicit not_empty(sync_buffer &b):that_(b){};
430          bool operator()() const { return !that_.empty(); }
431          sync_buffer &that_;
432      };
433  public:
434      BOOST_COPY_CONSTRUCTOR_DELETE(sync_buffer) 1
435      BOOST_COPY_ASSIGNEMENT_DELETE(sync_buffer) 2
436      sync_buffer():in_(0), out_(0) {}
437
438      bool full() { return out_==(in_+1)%(size+1); }
439      bool empty() { return out_==in_; }
440
441      unsigned get_in() {return in_;}
442      unsigned get_out() {return out_;}
443
444      void push(T v) {
445          synchronizer _(*this->mutex(), not_full_, not_full(*this)); 3
446          data_[in_]=v;
447          in_ = (in_+1)% (size+1);
448          not_empty_.notify_one(); 4
449      }
450
451      T pull() {
452          synchronizer _(*this->mutex(), not_empty_, not_empty(*this)); 5
453          unsigned idx = out_;
454          out_ = (out_+1)% (size+1);
455          not_full_.notify_one(); 6
456          return data_[idx];
457      }
458  };
459
460Monitors and conditions are useful for describing simple cases of shared objects (by simple we mean a limited use of conditions). If the conditions for delaying a calling component become complicated, the monitor may similarly become difficult to program and read.
461
462[endsect] [/Monitor Conditions]
463
464[endsect] [/Monitors]
465]
466
467[endsect] [/Internal Locking]
468
469
470