libs/thread/doc/internal_locking.qbk

   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
  13 Consider, for example, modeling a bank account class that supports simultaneous deposits and withdrawals from multiple locations (arguably the "Hello, World" of multithreaded programming).
  14
  15 From here a component is a model of the `Callable` concept.
  16
  17 I 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
  21 where `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
  23 The 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
  56 From 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
  61 The 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
  85 Execution of the `Deposit` and `Withdraw` operations will no longer be able to make simultaneous access to balance.
  86
  87 A 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
  89 With 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
 109 The 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
 114 The 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
 116 This approach is reasonably easy to implement and has an attractive simplicity. Unfortunately, "simple" might sometimes morph into "simplistic."
 117
 118 Internal 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
 120 The 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
 128 The problem is that between the two calls above, another thread can perform another operation on the account, thus breaking the second design requirement.
 129
 130 In 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
 138 Notice that the code above doesn't compile, the `mtx_` field is private.
 139 We have two possibilities:
 140
 141 * make `mtx_` public which seems odd
 142 * make the `BankAccount` lockable by adding the lock/unlock functions
 143
 144 We 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
 166 or inheriting from a class which add these lockable functions.
 167
 168 The `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
 190 and 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
 198 Notice 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
 203 As `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
 212 The 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
 226 Obviously, 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
 228 To 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
 236 The 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.
 237 We shall therefore introduce an abstraction that makes it easier to define such objects.
 238 The 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 an BasicLockable for the derived classes
 244   protected:
 245       typedef unspecified synchronizer; // is an strict lock guard
 246   };
 247
 248 [/shared_monitor]
 249 [/monitor]
 250
 251 A basic_monitor object behaves like a `BasicLockable` object but only for the inheriting classes.
 252 Protected 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
 294 In 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
 299 It 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
 300 follows:
 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
 320 The 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
 365 The 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
 412 We 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
 460 Monitors 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