libs/lockfree/doc/lockfree.qbk

   1 [library Boost.Lockfree
   2     [quickbook 1.4]
   3     [authors [Blechmann, Tim]]
   4     [copyright 2008-2009 Tim Blechmann]
   5     [category algorithms]
   6     [purpose
   7         lockfree concurrent data structures
   8     ]
   9     [id lockfree]
  10     [dirname lockfree]
  11     [license
  12         Distributed under the Boost Software License, Version 1.0.
  13         (See accompanying file LICENSE_1_0.txt or copy at
  14         [@http://www.boost.org/LICENSE_1_0.txt])
  15     ]
  16 ]
  17
  18 [c++]
  19
  20
  21 [/  Images   ]
  22
  23 [def _note_                         [$images/note.png]]
  24 [def _alert_                        [$images/caution.png]]
  25 [def _detail_                       [$images/note.png]]
  26 [def _tip_                          [$images/tip.png]]
  27
  28 [/  Links   ]
  29
  30 [def _lockfree_                      [^boost.lockfree]]
  31
  32 [/  unspecified stuff   ]
  33 [def __unspecified_int__ /unspecified-int-type/]
  34 [def __unspecified_bool__ /unspecified-bool-type/]
  35
  36 [section:disclaimer Disclaimer]
  37 _lockfree_ is NOT a boost library!
  38 [endsect]
  39
  40 [section Introduction]
  41
  42 [h2 What is _lockfree_?]
  43
  44 _lockfree_ provides implementations of lock-free data structures. Lock-free data structures can be accessed by multiple
  45 threads without the necessity of blocking synchronization primitives such as guards. Lock-free data structures can be
  46 used in real-time systems, where blocking algorithms may lead to high worst-case execution times, to avoid priority
  47 inversion, or to increase the scalability for multi-processor machines.
  48
  49 The following data structures are provided:
  50
  51 * [classref boost::lockfree::fifo], a lock-free fifo queue
  52 * [classref boost::lockfree::stack], a lock-free stack
  53 * [classref boost::lockfree::atomic_int], an atomic integer class
  54
  55 [endsect]
  56
  57
  58 [section Examples]
  59
  60 [h2 Atomic Integers]
  61
  62 The [classref boost::lockfree::atomic_int boost::lockfree::atomic_int] class implements fully synchronized atomic
  63 integers numbers.
  64
  65 ``
  66 #include <boost/thread/thread.hpp>
  67 #include <boost/lockfree/atomic_int.hpp>
  68 #include <iostream>
  69
  70 boost::lockfree::atomic_int<int> counter(0);
  71
  72 const int iterations = 10000000;
  73
  74 void increment_counter(void)
  75 {
  76     for (int i = 0; i != iterations; ++i)
  77         ++counter;
  78 }
  79
  80 void decrement_counter(void)
  81 {
  82     for (int i = 0; i != iterations; ++i)
  83         --counter;
  84 }
  85
  86 int main(int argc, char* argv[])
  87 {
  88     // incrementing counter in one thread, decrementing in another
  89     boost::thread thrd_inc(increment_counter);
  90     boost::thread thrd_dec(decrement_counter);
  91
  92     thrd_inc.join();
  93     thrd_dec.join();
  94
  95     std::cout << "counter value is " << counter << "." << std::endl;
  96 }
  97 ``
  98
  99 This program outputs the following:
 100
 101 [pre
 102 Counter value is 0.
 103 ]
 104
 105
 106
 107 [h2 Fifo]
 108
 109 The [classref boost::lockfree::fifo boost::lockfree::fifo] class implements a multi-writer/multi-reader fifo queue. The
 110 following example shows how integer values are produced and consumed by 2 threads each:
 111
 112 ``
 113 #include <boost/thread/thread.hpp>
 114 #include <boost/lockfree/atomic_int.hpp>
 115 #include <boost/lockfree/fifo.hpp>
 116 #include <iostream>
 117
 118 boost::lockfree::atomic_int<int> producer_count(0);
 119 boost::lockfree::atomic_int<int> consumer_count(0);
 120
 121 boost::lockfree::fifo<int> fifo;
 122
 123 const int iterations = 1000000;
 124
 125 void producer(void)
 126 {
 127     for (int i = 0; i != iterations; ++i) {
 128         int value = ++producer_count;
 129         fifo.enqueue(value);
 130     }
 131 }
 132
 133 void consumer(void)
 134 {
 135     int value;
 136     while (producer_count != 2*iterations) {
 137         while (fifo.dequeue(&value))
 138             ++consumer_count;
 139     }
 140
 141     while (fifo.dequeue(&value))
 142         ++consumer_count;
 143 }
 144
 145 int main(int argc, char* argv[])
 146 {
 147     boost::thread thrd_p1(producer);
 148     boost::thread thrd_p2(producer);
 149     boost::thread thrd_c1(consumer);
 150     boost::thread thrd_c2(consumer);
 151
 152     thrd_p1.join();
 153     thrd_p2.join();
 154     thrd_c1.join();
 155     thrd_c2.join();
 156
 157     std::cout << "produced " << producer_count << " objects." << std::endl;
 158     std::cout << "consumed " << consumer_count << " objects." << std::endl;
 159 }
 160 ``
 161
 162 The program output is:
 163
 164 [pre
 165 produced 2000000 objects.
 166 consumed 2000000 objects.
 167 ]
 168
 169
 170 [h2 Stack]
 171
 172 The [classref boost::lockfree::stack boost::lockfree::stack] class implements a multi-writer/multi-reader stack. The
 173 following example shows how integer values are produced and consumed by 2 threads each:
 174
 175 ``
 176 #include <boost/thread/thread.hpp>
 177 #include <boost/lockfree/atomic_int.hpp>
 178 #include <boost/lockfree/stack.hpp>
 179 #include <iostream>
 180
 181 boost::lockfree::atomic_int<int> producer_count(0);
 182 boost::lockfree::atomic_int<int> consumer_count(0);
 183
 184 boost::lockfree::stack<int> stack;
 185
 186 const int iterations = 1000000;
 187
 188 void producer(void)
 189 {
 190     for (int i = 0; i != iterations; ++i) {
 191         int value = ++producer_count;
 192         stack.push(value);
 193     }
 194 }
 195
 196 void consumer(void)
 197 {
 198     int value;
 199     while (producer_count != 2*iterations) {
 200         while (stack.pop(&value))
 201             ++consumer_count;
 202     }
 203
 204     while (stack.pop(&value))
 205         ++consumer_count;
 206
 207 }
 208
 209 int main(int argc, char* argv[])
 210 {
 211     boost::thread thrd_p1(producer);
 212     boost::thread thrd_p2(producer);
 213     boost::thread thrd_c1(consumer);
 214     boost::thread thrd_c2(consumer);
 215
 216     thrd_p1.join();
 217     thrd_p2.join();
 218     thrd_c1.join();
 219     thrd_c2.join();
 220
 221     std::cout << "produced " << producer_count << " objects." << std::endl;
 222     std::cout << "consumed " << consumer_count << " objects." << std::endl;
 223 }
 224 ``
 225 The program output is:
 226
 227 [pre
 228 produced 2000000 objects.
 229 consumed 2000000 objects.
 230 ]
 231
 232
 233
 234 [endsect]
 235
 236
 237 [section Reference]
 238
 239 [section boost::lockfree::fifo]
 240
 241 [classref boost::lockfree::fifo boost::lockfree::fifo] provides a multi-writer/multi-reader lockfree fifo class,
 242 enqueueing and dequeueing is lockfree, construction/destruction has to be synchronized. A specialized [classref
 243 boost::lockfree::fifo fifo] class for pointer-arguments is provided, which supports dequeueing to stl/boost-style smart
 244 pointers. Its used type argument is limited to PODs.
 245
 246 It uses a freelist for memory management, freed nodes are pushed to the freelist, but not returned to the os. This may
 247 result in leaking memory.
 248
 249 [section Synopsis]
 250
 251 [c++]
 252
 253
 254 ``
 255 namespace boost {
 256 namespace lockfree {
 257
 258 template <typename T, typename freelist_t = caching_freelist_t, typename Alloc = std::allocator<T> >
 259 class fifo:
 260     boost::noncopyable
 261 {
 262 public:
 263     fifo(void);
 264     explicit fifo(std::size_t initial_nodes);
 265     ~fifo(void);
 266
 267     bool empty(void) const;
 268
 269     bool enqueue(T const & t);
 270     bool dequeue(T * ret);
 271 };
 272
 273 template <typename T, typename freelist_t = caching_freelist_t, typename Alloc = std::allocator<T> >
 274 class fifo<T*>:
 275     boost::noncopyable
 276 {
 277 public:
 278     fifo(void);
 279     explicit fifo(std::size_t initial_nodes);
 280     ~fifo(void);
 281
 282     bool empty(void) const;
 283
 284     bool enqueue(T * t);
 285
 286     bool dequeue (T ** ret);
 287     bool dequeue (std::auto_ptr<T> & ret);
 288     bool dequeue (boost::scoped_ptr<T> & ret);
 289     bool dequeue (boost::shared_ptr<T> & ret);
 290 };
 291
 292 } /* namespace lockfree */
 293 } /* namespace boost */
 294 ``
 295
 296 [endsect]
 297
 298 [section Members]
 299
 300 [heading Constructors]
 301
 302     fifo(void);
 303
 304 Default Constructor
 305
 306     explicit fifo(std::size_t initial_nodes);
 307
 308 Construct fifo with a number of initially allocated fifo nodes.
 309
 310 [heading Destructor]
 311
 312     ~fifo(void);
 313
 314 Destroys stored nodes and fifo, free all nodes from freelist.
 315
 316 [warning Not thread-safe, no enqueue/dequeue operation is allowed, when the destructor is running]
 317
 318 [heading Empty]
 319
 320     bool empty(void) const;
 321
 322 Returns: true, if fifo is empty.
 323
 324 [warning Not thread-safe, use for debugging purposes only]
 325
 326
 327 [heading Enqueue]
 328
 329     bool enqueue(T const & t);
 330
 331 Enqueues object t to the fifo. Enqueueing may fail, if the freelist is not able to allocate a new fifo node.
 332
 333 Returns: true, if the enqueue operation is successful.
 334
 335 [note Thread-safe and non-blocking]
 336 [important May block if node needs to be allocated from the operating system]
 337
 338 [heading Dequeue]
 339
 340     bool dequeue (T * ret);
 341
 342 Dequeue object from fifo.
 343
 344 Returns: true, if the dequeue operation is successful, false if fifo was empty.
 345
 346 Effect: if dequeue operation is successful, object is written to memory location denoted by ret.
 347
 348 [note Thread-safe and non-blocking]
 349
 350     bool dequeue (std::auto_ptr<T> & ret);
 351     bool dequeue (boost::scoped_ptr<T> & ret);
 352     bool dequeue (boost::shared_ptr<T> & ret);
 353
 354 The specialized class for pointer objects provides an api for dequeuing objects directly to smart pointers.
 355
 356 [endsect]
 357
 358 [section Memory Management]
 359
 360 The memory management of the fifo can be controlled via its `freelist_t` template argument. Two different freelists can
 361 be used. `struct caching_freelist_t` selects a caching freelist, which can allocate more nodes from the operating
 362 system, and `struct static_freelist_t` uses a fixed-sized freelist. With a fixed-sized freelist, the enqueue operation
 363 may fail, while with a caching freelist, the enqueue operation may block.
 364
 365 [endsect]
 366
 367
 368 [endsect]
 369
 370 [section boost::lockfree::stack]
 371
 372 [classref boost::lockfree::stack boost::lockfree::stack] provides a multi-writer/multi-reader lockfree stack class,
 373 push and pop is lockfree, construction/destruction has to be synchronized.
 374
 375 It uses a caching freelist for memory management, freed nodes are pushed to the freelist. This may result in leaking
 376 memory.
 377
 378 [section Synopsis]
 379
 380 [c++]
 381
 382
 383 ``
 384 namespace boost {
 385 namespace lockfree {
 386
 387 template <typename T, typename Alloc = std::allocator<T> >
 388 class stack:
 389     boost::noncopyable
 390 {
 391 public:
 392     stack(void);
 393     explicit stack(std::size_t n);
 394
 395     bool empty(void) const;
 396
 397     bool push(T const & v);
 398     bool pop(T * ret);
 399 };
 400
 401 } /* namespace lockfree */
 402 } /* namespace boost */
 403 ``
 404
 405 [endsect]
 406
 407 [section Members]
 408
 409 [heading Constructors]
 410
 411     stack(void);
 412
 413 Default Constructor
 414
 415     explicit stack(std::size_t initial_nodes);
 416
 417 Construct stack with a number of initially allocated stack nodes.
 418
 419
 420 [heading Destructor]
 421
 422     ~stack(void);
 423
 424 Destroys stack, free all nodes from freelist.
 425
 426 [heading Empty]
 427
 428     bool empty(void) const;
 429
 430 Returns: true, if stack is empty.
 431
 432 [warning Not thread-safe, use for debugging purposes only]
 433
 434
 435 [heading Push]
 436
 437     bool push(T const & t);
 438
 439 Pushes object t to the stack. Pushing may fail, if the freelist is not able to allocate a new stack node.
 440
 441 [note Thread-safe and non-blocking]
 442 [important May block, if node needs to be allocated from the operating system]
 443
 444 [heading Pop]
 445
 446     bool pop (T * ret);
 447
 448 Pop object from stack.
 449
 450 Returns: true, if the pop operation is successful, false if stack was empty.
 451 Effect: if pop operation is successful, object is written to memory location denoted by ret.
 452
 453 [note Thread-safe and non-blocking]
 454
 455 [endsect]
 456
 457 [section Memory Management]
 458
 459 The memory management of the stack can be controlled via its `freelist_t` template argument. Two different freelists can
 460 be used. `struct caching_freelist_t` selects a caching freelist, which can allocate more nodes from the operating
 461 system, and `struct static_freelist_t` uses a fixed-sized freelist. With a fixed-sized freelist, the push operation
 462 may fail, while with a caching freelist, the push operation may block.
 463
 464 [endsect]
 465
 466 [endsect]
 467
 468 [section boost::lockfree::atomic_int]
 469
 470 [classref boost::lockfree::atomic_int boost::lockfree::atomic_int] provides an implementation for atomic integers. It
 471 does not provide the full interface of integer numbers, but a limited subset, that can be implemented with atomic
 472 operations. Modifying an atomic integer acts as full memory barrier.
 473
 474 [section Synposis]
 475
 476 ``
 477 namespace boost {
 478 namespace lockfree {
 479
 480 template <typename T>
 481 class boost::lockfree::atomic_int:
 482 {
 483 public:
 484     explicit atomic_int(T v = 0);
 485
 486     operator T(void) const;
 487     void operator =(T v);
 488
 489     T operator +=(T v);
 490     T operator -=(T v);
 491
 492     T operator ++(void);
 493     T operator --(void);
 494
 495     T operator ++(int);
 496     T operator --(int);
 497 };
 498
 499 } /* namespace lockfree */
 500 } /* namespace boost */
 501 ``
 502
 503 [endsect]
 504
 505 [section Members]
 506
 507 [heading Constructor]
 508
 509     explicit atomic_int(T v = 0);
 510
 511 Initializes atomic_int to value v
 512
 513
 514 [heading Conversion]
 515     operator T(void) const;
 516
 517 Returns: Integer value of atomic_int
 518
 519 [heading In-Place Operators]
 520
 521     T operator +=(T v);
 522
 523 Returns: T(*this) + v
 524
 525 Effect: T(*this) = T(*this) + v
 526
 527     T operator -=(T v);
 528
 529 Returns: T(*this) - v
 530
 531 Effect: T(*this) = T(*this) - v
 532
 533
 534 [heading Prefix Operators]
 535
 536     T operator ++(void);
 537
 538 Effect: increments value
 539
 540 Returns: value before incrementing
 541
 542     T operator --(void);
 543
 544 Effect: decrements value
 545
 546 Returns: value before decrementing
 547
 548 [heading Postfix Operators]
 549
 550     T operator ++(int);
 551
 552 Effect: increments value
 553
 554 Returns: value after incrementing
 555
 556     T operator --(int);
 557
 558 Effect: decrements value
 559
 560 Returns: value after decrementing
 561
 562
 563 [endsect]
 564
 565 [endsect]
 566
 567 [endsect]
 568
 569 [/
 570
 571 [section Building blocks]
 572 The _lockfree_ library provides several building blocks, used in lockfree algorithms.
 573
 574
 575 [section tagged_ptr]
 576
 577 Tagged pointer implementation as smart pointer class, as it is required by several lockfree algorithms.
 578
 579 [section Synposis]
 580 ``
 581 namespace boost
 582 {
 583 namespace lockfree
 584 {
 585
 586 template <class T>
 587 class tagged_ptr
 588 {
 589 public:
 590     typedef __unspecified_int__ tag_t;
 591
 592     tagged_ptr(void);
 593     tagged_ptr(tagged_ptr const & p);
 594     explicit tagged_ptr(T * p, tag_t t = 0);
 595
 596     void operator= (tagged_ptr const & p);
 597     void atomic_set(tagged_ptr const & p);
 598     void atomic_set(T * p, tag_t t);
 599
 600     void set(tagged_ptr const & p);
 601     void set(T * p, tag_t t);
 602
 603     bool operator== (tagged_ptr const & p) const;
 604     bool operator!= (tagged_ptr const & p) const;
 605
 606     T * get_ptr() const;
 607     void set_ptr(T * p);
 608
 609     tag_t get_tag() const;
 610     void set_tag(tag_t t);
 611
 612     bool cas(tagged_ptr const & oldval, T * newptr);
 613     bool cas(tagged_ptr const & oldval, T * newptr, tag_t t);
 614
 615     T & operator*() const;
 616     T * operator->() const;
 617
 618     operator __unspecified_bool__(void) const;
 619 };
 620
 621 } /* namespace lockfree */
 622 } /* namespace boost */
 623
 624 ``
 625 [endsect]
 626
 627 [section Members]
 628
 629 [heading tag_t]
 630
 631     typedef __unspecified_int__ tag_t;
 632
 633 Type of ABA-prevention tag
 634
 635 [heading Constructors]
 636
 637     tagged_ptr(void);
 638
 639 Uninitialized constructor
 640
 641     tagged_ptr(tagged_ptr const & p);
 642
 643 Copy Constructor
 644
 645     explicit tagged_ptr(T * p, tag_t t = 0);
 646
 647 Construct tagged_ptr from pointer and tag
 648
 649
 650 [heading Atomically Set]
 651
 652     void operator= (tagged_ptr const & p);
 653     void atomic_set(tagged_ptr const & p);
 654
 655 Atomically set from tagged_ptr.
 656
 657     void atomic_set(T * p, tag_t t);
 658
 659 Atomically set from pointer and tag
 660
 661 [heading Set]
 662     void set(tagged_ptr const & p);
 663
 664 Set from tagged_ptr
 665
 666     void set(T * p, tag_t t);
 667
 668 Set from pointer and tag
 669
 670 [heading Comparison]
 671     bool operator== (tagged_ptr const & p) const;
 672     bool operator!= (tagged_ptr const & p) const;
 673
 674 Returns: (get_ptr() == p.get_ptr()) && (get_tag() == p.get_tag())
 675
 676 [heading Pointer access]
 677
 678     T * get_ptr() const;
 679
 680 Get pointer
 681
 682     void set_ptr(T * p);
 683
 684 Set pointer
 685
 686
 687 [heading Tag access]
 688
 689     tag_t get_tag() const;
 690
 691 Get tag
 692
 693     void set_tag(tag_t t);
 694
 695 Set tag
 696
 697 [heading Compare-And-Swap]
 698
 699     bool cas(tagged_ptr const & oldval, T * newptr);
 700
 701 if (*this == oldval) {
 702     this->set(newptr, oldval.get_tag() + 1);
 703     return true;
 704 }
 705 else
 706     return false;
 707
 708     bool cas(tagged_ptr const & oldval, T * newptr, tag_t t);
 709
 710 if (*this == oldval) {
 711     this->set(newptr, t);
 712     return true;
 713 }
 714 else
 715     return false;
 716
 717 [heading Indirection]
 718     T & operator*() const;
 719
 720 Returns: reference to object, undefined if get_ptr() == 0
 721
 722     T * operator->() const;
 723
 724 Returns: pointer to object
 725
 726 [heading Conversion]
 727
 728     operator __unspecified_bool__(void) const;
 729
 730 Returns: get_ptr() != 0
 731
 732
 733 [endsect]
 734
 735 [endsect]
 736
 737 [section Freelists]
 738
 739 [section Freelist Concept]
 740
 741 ``
 742 template <typename T, typename Alloc = std::allocator<T> >
 743 concept freelist
 744 {
 745 public:
 746     freelist(void);
 747     explicit freelist(std::size_t initial_nodes);
 748     ~freelist(void);
 749
 750     T * allocate (void);
 751     void deallocate (T * n);
 752 };
 753 ``
 754
 755 [endsect]
 756
 757
 758 [section Members]
 759
 760
 761 [heading Constructors]
 762
 763     freelist(void);
 764
 765 Default Constructor
 766
 767     explicit freelist(std::size_t initial_nodes);
 768
 769 Construct freelist, allocate a number of initial nodes
 770
 771
 772 [heading Destructor]
 773
 774     ~freelist(void);
 775
 776 Free all nodes from the freelist to the OS
 777
 778
 779 [heading Allocation]
 780
 781     T * allocate (void);
 782
 783 Allocate memory for one object.
 784
 785
 786 [heading Deallocation]
 787
 788     void deallocate (T * n);
 789
 790 Deallocate object to freelist
 791
 792 [endsect]
 793
 794 [section Freelist Implementations]
 795
 796     template <typename T, typename Alloc = std::allocator<T> >
 797     class caching_freelist;
 798
 799 Caching freelist class. Uses an internal lockfree stack to cache objects. Deallocation never frees objects.
 800
 801     template <typename T, std::size_t max_size = 64,
 802               typename Alloc = std::allocator<T> >
 803     class freelist;
 804
 805 Freelist class, with a maximum size of max_size. Uses an lockfree stack to cache max_size objects.
 806
 807 [endsect]
 808 [endsect]
 809 [endsect]
 810
 811 ]
 812
 813 [/
 814
 815 [section Primitives]
 816 The _lockfree_ library provides platform-specific wrappers for low-level operations.
 817
 818 [section Memory Barriers]
 819     void boost::lockfree::detail::memory_barrier(void);
 820
 821 Full Memory Barrier.
 822
 823 [endsect]
 824
 825 [section Compare-and-Swap]
 826
 827 Lockfree on supported platforms, otherwise blocking emulation.
 828
 829     template <class C>
 830     inline bool boost::lockfree::detail::atomic_cas(volatile C * addr, C old, C nw);
 831
 832 Single-word compare-and-swap
 833
 834     template <class C, class D, class E>
 835     inline bool boost::lockfree::detail::atomic_cas2(volatile C * addr, D old1, E old2, D new1, E new2);
 836
 837 Double-word compare-and-swap
 838
 839 [endsect]
 840
 841 [endsect]
 842
 843 ]
 844
 845 [section Portability]
 846
 847 Most data structures of _lockfree_ are written to use of Compare-And-Swap instructions. In order to implement the
 848 tagged_ptr, CAS instructions are required, that can operate on one pointer and one integer type. For non-supported
 849 platforms, a blocking emulation of the atomic instructions is provided.
 850
 851 Tested architectures:
 852
 853 * x86
 854 * x86_64
 855
 856 Tested compilers:
 857
 858 * gcc-4.2, gcc-4.3, gcc-4.4
 859
 860
 861 [endsect]
 862
 863 [section Acknowledgements]
 864
 865 Thanks for suggestions, porting, testing:
 866
 867 * Thomas Grill, original win32/osx code pieces
 868 * Shiwei Xu, api suggestions
 869 * Stefan Eilemann, bug fixes
 870 * Mignon Belongie, bug fix
 871 * Anthony Williams, found fifo race condition
 872 * Casey McCandless, msvc/icc fixes
 873 * Mark Bulas, msvc/x64 fixes
 874 * Anteru, api/documentation suggestions
 875
 876 [endsect]
 877
 878 [section References]
 879
 880 # Maged M. Michael and Michael L. Scott. Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms. In Symposium on Principles of Distributed Computing, pages 267–275, 1996.
 881 # M. Herlihy, V. Luchangco, P. Martin, and M. Moir. Nonblocking memory management support for dynamic-sized data
 882 structures. ACM Transactions on Computer Systems (TOCS), 23(2):146–196, 2005.
 883
 884
 885 [endsect]
 886
 887
 888 [section Todo]
 889
 890 # Compare-And-Swap instructions return the old value, one can make use of this in order to avoid an additional memory
 891 access (suggested by Cory Nelson).
 892 # Adapt algorithms to be lockfree on architectures with load-linked/store-conditional instructions.
 893
 894 [endsect]