Concurrent @concurrent package (version 1.8)

JAVA concurrent source code version 1.8

  • Concurrent @concurrent package (version 1.8)
    • 1. Concurrency mechanism
      • 1.1 Principles of Concurrency
      • 1.2 Common Concurrency mechanisms
      • 1.3 Concurrency mechanism of different systems
    • 2. The mutex
      • 2.1 Mutual exclusion Requirements
      • 2.2 Mutually exclusive Scheme
      • 2.3 Mutually exclusive software method support
        • 2.3.1 Dekker algorithm
        • 2.3.2 Peterson algorithm
      • 2.4 Mutually exclusive hardware support
        • 2.4.1 Interruption Disabled
          • 2.4.1.1 Overview of interrupt disabling
          • 2.4.1.2 Interruption disabling Problem
        • 2.4.2 Special Machine instructions
          • 2.4.2.1 Overview of special machine instructions
          • 2.4.2.2 Special machine instruction problem
      • 2.5 Mutually exclusive system or language level support
        • 2.5.1 semaphore
          • 2.5.1.1 Semaphore Overview
          • 2.5.1.2 Semaphore Implementation (CAS version)
          • 2.5.1.3 The semaphore is mutually exclusive
        • 2.5.2 tube side
          • 2.5.2.1 Pipe Process Overview
          • 2.5.2.2 Conditional variables
          • 2.5.2.3 Pipe Process use
        • 2.5.3 Message Passing
          • 2.5.3.1 Overview of Messaging
          • 2.5.3.2 Message Structure
          • 2.5.3.3 Message Communication status
          • 2.5.3.3 Message communication combination
          • 2.5.3.4 Message communication addressing
          • 2.5.3.5 Message Communication is mutually exclusive
        • 2.5.4 Read/Write Priority
    • 3. The Concurrent and contract
      • 3.1 Overall architecture of Concurrent package
      • 3.2 Overall Class diagram of the Concurrent package
      • 3.3 Concurrent package implementation mechanism
        • 3.3.1 Low-level – Hardware instruction support
        • 3.3.2 Middle Layer – Basic data structure + algorithm support
        • 3.3.3 High Level – Concurrent class library support
  • KiraSally’s nuggets blog thanks for your support
  • Thank you<< Essence and Design Principle of operating System (original book sixth Edition) >>

1. Concurrency mechanism

1.1 Principles of Concurrency

  • Single-core system: Threads are executed alternately, giving a sense of simultaneous execution because the alternately are so fast and numerous
  • Multicore systems: not only can threads of execution be alternated, but threads of execution can be overlapping
  • Note: Concurrency in this chapter mainly refers to concurrency between threads

1.2 Common Concurrency mechanisms

1.3 Concurrency mechanism of different systems

  • UNIX: pipes, messages, shared memory, semaphore, signals
  • Linux kernel: Atomic operations, spinlocks, semaphores, barriers (this is the most important thing to know since servers are typically located on Linux servers)
  • Solaris thread synchronization primitives: mutex, semaphore, multi-reader/single-writer lock, condition variable
  • Windows: Wait functions, dispatcher objects, critical sections, lightweight read/write locks, and condition variables

2. The mutex

2.1 Mutual exclusion Requirements

  • In order to provide support for mutex, the following requirements must be met:
  • Mutual exclusion mandatory: When a critical section is shared, only one thread is allowed to enter the critical section at a time, that is, mutual exclusion must be enforced
  • Disable interference: A thread that stops in a non-critical section cannot interfere with other threads, including critical and non-critical sections
  • Disable infinite delay: Never allow threads that need access to a critical section to be indefinitely delayed, such as deadlock or starvation
  • Emergent: Any thread that needs to enter a critical section must be able to do so immediately when there are no threads in the critical section
  • Core independent: There are no requirements or restrictions on the speed of execution of related threads or on the number of processors
  • Finite time: A thread must remain in a critical section for a finite amount of time

2.2 Mutually exclusive Scheme

  • Hardware support: Mutually exclusive instructions are natively supported by the processor, which has the benefit of reducing overhead, but is hardly a universal solution
  • System or language level support: that is, the operating system or program language provides this level of mutually exclusive support, such as semaphore, pipe, message passing, and so on
  • Software method support:These methods are usually based on the assumption that access to memory is essentially mutually exclusive. Although the order in which access is allowed is not specified in advance, simultaneous access to the same address in memory is serialized by the memory arbiter. That is, it is understandable to solve the mutual exclusion problem algorithmically, for exampleDekker algorithm,Peterson algorithm

2.3 Mutually exclusive software method support

  • Summary: The software approach is to achieve mutual exclusion through algorithm, that is to serialize critical access from the perspective of algorithm, it does not consider the support of hardware, operating system or programming language, the most famous is Dekker algorithm and its concise version Peterson algorithm (algorithm name is inventor).

2.3.1 Dekker algorithm

/** * The basic constraints of the Dekker algorithm are: * Only one access can be made to a memory location at a time * 1. Set flag as the key for two threads to enter the critical area. When one thread fails, other threads can still access * - Each thread can only change its own flag, but can only check the flag of other threads. * - When a thread wants to enter the critical area, it needs to periodically check the flag of another thread. Until another thread is not in the critical area * - when the thread enters the critical area, it should immediately set its flag to true, indicating the occupation of the critical area * - when the thread leaves the critical area, it should immediately set its flag to false, indicating the release of the critical area * 2. The access thread must read the turn value repeatedly until it is allowed to enter the critical section * - When the turn value is equal to the thread number, the thread can enter its critical section * - otherwise, The thread must be forced to wait (busy or spin wait) */ public class Dekker {// Observe the state of two threads Boolean [] flag = {false,false}; Int turn = 1; int turn = 1; Public void P0(){while (true){// Set P0's flag to true and check P1's flag[0] = true; While (flag[1]){if (turn == 1){// If (turn == 1){// If (turn == 1){// If (turn == 1){// If (turn == 1){ Flag [0] = false; P0 while (turn == 1){/** do Nothing empty spin **/} flag[0] = true; }} // When P1 flag is false, P0 can enter the critical section immediately /** critical section **/ / When the critical section is completed, turn is set to 1, // Set the flag of P0 to false, release the critical section, so that P1 can enter the critical section turn = 1; flag[0] = false; /** do otherThings **/}} public void P1(){while (true){// Set P1's flag to true and check P0's flag[1] = true; If (turn == 0){// If (turn == 0){// If (turn == 0){// If (turn == 0){// If (turn == 0){// If (turn == 0){ Flag [1] = false; While (turn == 0){/** do Nothing empty spin **/} flag[1] = true; }} // When P0 flag is false, P1 can enter critical section **/ / When critical section is completed, turn is set to 0, // Set P1 flag to false, release the critical section, so that P0 can enter the critical section turn = 0; flag[1] = false; /** do otherThings **/}} public static void main(){** do otherThings **/}} public static void main(){** do otherThings **/}}Copy the code

2.3.2 Peterson algorithm

/** * Peterson is simpler and better than Dekker and can be easily generalized to multiple threads * 1. Mutually exclusive protection verification: P0 Angle * - when PO sets flag[0]=true, P1 cannot enter the critical zone * - when P1 has entered the critical zone and Flag [1]=true, P0 cannot enter the critical zone * 2. Avoid mutual blocking validation: P0 Angle * - When P0 is blocked in the while loop, flag[1]=true and turn=1 * - When Flag [1]=false or turn=0, P0 can enter the critical section * 3. Public class Peterson {Boolean [] flag = {false,false}; public class Peterson [] flag = {false,false}; // indicate the position of each mutex thread int turn = 0; Public void P0(){while (true){flag[0] = true; // Set turn=1 explicitly each time as a while empty spin condition, forcing other threads to have the chance to enter the critical section // This is also a concise solution to solve the mutex. While (flag[1] && turn == 1){/** do Nothing empty spin **/} /** critical section critical section **/ flag[0] = false; /** do otherThings **/ } } public void P1(){ while (true){ flag[1] = true; turn = 0; While (flag[0] && turn == 0){/** do Nothing empty spin **/} /** critical section critical section **/ flag[1] = false; /** do otherThings **/}} public static void main(){** do otherThings **/}} public static void main(){** do otherThings **/}}Copy the code

2.4 Mutually exclusive hardware support

2.4.1 Interruption Disabled

2.4.1.1 Overview of interrupt disabling
  • Principle: single-core system, concurrent threads can not overlap can only alternate; A thread will run until it calls a system service or is interrupted
  • Implementation: To ensure mutual exclusion, as long as one thread is not interrupted, it can be provided through the system kernel for enabling or disabling interrupt defined primitives
  • Interrupt disabled pseudo-code implementation
// Since critical sections cannot be interrupted, So mutual exclusion is guaranteed while(true){/** disable interrupt disables interrupts **/ /** critical zone **/ /** enable interrupt enables interrupts **/ /** do Other Other parts **/}Copy the code
2.4.1.2 Interruption disabling Problem
  • Low efficiency: the cost of this method is high, the processor is limited to alternate execution, the efficiency is significantly reduced
  • Multi-core not supported: This method cannot be used with multi-processor architectures, where multiple threads are likely to execute simultaneously

2.4.2 Special Machine instructions

2.4.2.1 Overview of special machine instructions
  • Prerequisite: In a multi-core system, memory is shared between processors and there is no mutually exclusive interrupt mechanism
  • Principle: At the hardware level, access to a storage unit excludes other access to the same unit. During the execution of a dedicated instruction, any other instruction accessing memory is blocked, and these actions are completed within an instruction cycle
  • Implementation:Two commonly used machine instructions are the Exchange instruction and the compare and exchange instruction CAS(see authors’ article)And @CAS)
2.4.2.2 Special machine instruction problem
  • Use busy wait: Continues to consume processor time while waiting
  • Possible starvation: Threads entering a critical section are random and may cause some processes to be denied entry indefinitely
  • Possible deadlocks: for example, the current thread is interrupted after entering the critical section, and a new thread (with higher priority) that enters the critical section tries to use the same resource, is rejected and enters the busy loop waiting, but will never be scheduled to execute due to the lower priority of the original thread

2.5 Mutually exclusive system or language level support

2.5.1 semaphore

2.5.1.1 Semaphore Overview
  • Rationale: N threads can cooperate through simple signals, so that a thread can be forced to stop at a certain location until it receives a special signal. Any complex need for cooperation can be satisfied with an appropriate signal structure
  • Components:

    • To signal, a special variable, SEM, called a semaphore, is used, usually initialized to non-negative values
    • To transmit signals through semaphore SEM, the thread can execute semSignal(SEM) : when semaphore SEM +1, when SEM is less than or equal to 0, the thread blocked by semWait is blocked
    • To receive signals through semaphore SEM, a thread can execute the primitive semWait(sem) : semaphore SEM-1, when SEM becomes negative, the thread executing semWait is blocked, otherwise the thread continues to execute
  • Classification:Both counting semaphores and binary semaphores require the use of queues to hold processes/threads waiting on the semaphore. This requires deciding in what order processes are removed from the queue

    • 1. A semaphore (often used) that uses a FIFO first-see, first-out fair policy (i.e. the process/thread that has been blocked the longest is released from the queue first).
    • Weak semaphore: A semaphore in which no process/thread is required to remove the order from the queue
  • Addendum: Binary semaphores differ only in that sem values can only be 0 and 1
2.5.1.2 Semaphore Implementation (CAS version)
/** * Design principles: Only one thread can control a semaphore at any time with wait and signal operations * Requirements: semWait and semSingal operations must be implemented as atomic primitives * Properties of semaphore semaphore (sem) * flag: If the semaphore is available, the default is 0 * count: * When >=0, indicates the number of threads that can perform semWait without being suspended * When <0, indicates the number of threads that can be suspended in the semaphore wait queue * queue: SemWait (sem){// If sem.flag is not 0, spin wait until sem.flag is 0. Busy waiting ensures that queue operations are synchronized, but because wait and signal take a short time to execute, the overhead is small while(! Compare_and_swap (sem. The flag, 0, 1)); sem.count--; If (sem.count < 0){/** The thread enters sem.queue and blocks **/} sem.flag = 0; } semSignal(sem){// If sem.flag is not 0, spin wait until 0 while(! Compare_and_swap (sem. The flag, 0, 1)); sem.count++; If (sem.count <= 0){** * from sem.queue, the thread is in the ready queue **/} sem.flag = 0; }Copy the code
2.5.1.3 The semaphore is mutually exclusive
Final int n = /** thread count **/ int s = 1; //semaphore public void P(int i){ while(true){ semWait(s); /** Critical zone **/ semSignal(s); /** do other parts **/}}Copy the code

2.5.2 tube side

2.5.2.1 Pipe Process Overview
  • Definition: A pipe program is a software module consisting of one or more procedures, an initialization sequence, and local data
  • Features:

    • Local data variables can only be accessed by the procedures of the management, not by any external procedures
    • A thread enters a pipe by calling a procedure of the pipe
    • Only one thread can be executing in the pipe at any time, and any other threads calling the pipe will be blocked waiting for the pipe to become available
  • Synchronization mechanism:For pipe procedures, a mechanism (condition variable) is needed to achieve the following two effects:

    • When a thread calls a pipe, it must be suspended until a condition is met and the pipe can be released so that other threads can access it
    • When conditions are met and the pipe is available again, the thread is restored and allowed to re-enter the pipe at the suspension point to continue with subsequent operations
2.5.2.2 Conditional variables
  • Summary: A pipe provides support for synchronization through the use of condition variables, which are contained and accessed only by the pipe
  • Operation:There are two functions that manipulate condition variables

    • Cwait (c): Execution of the calling thread is suspended on condition C, and the procedure can now be used by another thread
    • Csignal (c) : Resumes a thread whose execution has been suspended after cWAIT due to certain conditions. If multiple threads are suspended, one of them is selected to resume execution at the starting point according to the queuing policy
2.5.2.3 Pipe Process use
  • Use: monitor is a useful technique, we can use the monitor lock any object, such as for a similar list of objects, you can use a lock to lock the entire list, also can use a lock, each table for each element in a table with a lock (lenovo Concurent package for the concurrent data structures, feel very kind? ~); At the same time, the pipe provides support for synchronization through Condition variables, such as Condition, which is particularly suitable for producer-consumer business scenario processing

2.5.3 Message Passing

2.5.3.1 Overview of Messaging
  • Message definition: Message passing refers to threads communicating with each other by sending messages
  • Message implementation:A pair of primitive implementations are usually providedsend(destination,message) 、receive(source,message)
  • Sending messages: One thread sends a message as a massage to another specified target destination thread;
  • Receive messages: The thread receives messages massage from the source thread by executing the ReciEVE primitive
2.5.3.2 Message Structure
  • Message type: The type of message specified by which the receiver tends to listen for and capture messages
  • Destination ID/ Source ID: identifier of sender/source
  • Message length: The total length of the entire message
  • Control information: Additional information, such as Pointers to create message lists, records the number of messages passed between sources and targets, order and ordinal, and priority
  • Message content: The Body of the message
  • Addendum: Readers can refer to the package formats of various protocols in ISO, such as HTTP and TCP

2.5.3.3 Message Communication status
  • Send: Either the sending thread blocks until the message is received by the target thread, or it does not block
  • receive:

    • If the message has been sent before it is received, the message is received by the target thread and continues execution
    • If there is no waiting message, the target thread blocks until the waiting message arrives, or the thread continues to execute, giving up receiving

2.5.3.3 Message communication combination
  • Block send, block receive: Both the sender and the receiver are blocked until the message is delivered
  • Non-blocking send, non-blocking recive: does not require either party to wait
  • Receive: The sender can continue after sending the requested message, but the receiver is blocked until the requested message arrives. The most typical application is the server, which allows other services to send multiple messages to it as soon as possible. The receiving thread must continue working after the message arrives, or it will be blocked
2.5.3.4 Message communication addressing
  • Addressing: Refers to the method of determining the source and destination of a message, that is, identifying the source and destination address of the message
  • Classification: direct and indirect addressing
  • Direct addressing: The send primitive contains the destination address, and the receive primitive is divided into two types of processing. Direct: Requires the receiver to display the specified sender, the receiver must know the source address in advance, and only receives the message from the sender implicitly: When the sender is not expected, the recieve primitive’s source must retain the return address after the receive operation has been performed
  • Indirect addressing: Messages are not sent directly from the sender to the receiver, but the two share a data structure consisting of a queue that temporarily holds messages, called a mailbox. The sender sends messages to the mailbox, and the receiver takes messages from the mailbox, thus decoupling the sender and receiver
2.5.3.5 Message Communication is mutually exclusive
  • Suppose a group of concurrent threads share a mailbox box(for storing messages) that is initialized to a message with no content
  • A thread wishing to enter a critical section first attempts to receive a message, and if the mailbox is empty, the thread is blocked
  • Once the thread gets the message, it goes to the critical section and puts the message back into the mailbox
  • A message function can be thought of as a token passed between threads
Void P(int I){Message MSG = /* Message */ while(true){receive(box, MSG); Send (box, MSG)}} send(box,null); // The mailbox is initialized as a message with no contentCopy the code

2.5.4 Read/Write Priority

  • Literacy problems:Threads share a data area. Some threads are read-only, while others are read-write. In this case, the reader thread does not need to exclude other readers, but the writer thread needs to exclude all other threads

    • Any number of reader threads can read the data area simultaneously
    • Only one writer thread can write to the data area at a time
    • If a writer thread is writing data, disallow any read operations by the reader thread
  • Read and write policies:In order to provide concurrency performance, we can operate the writer-first policy in the case of read more than write lessConcurrent @ ReentrantReadWriteLockOr COW (whichever comes first)

3. The Concurrent and contract

3.1 Overall architecture of Concurrent package

3.2 Overall Class diagram of the Concurrent package

3.3 Concurrent package implementation mechanism

  • Review:In the overall package design, Master Doug Lea adopted3.1 Overall architecture of Concurrent packageThree layers of structure
  • Supplement: The author will introduce corresponding explanations about the contents involved in the package delivery, please look forward to it (the progress depends on the author’s busy degree).

3.3.1 Low-level – Hardware instruction support

  • Summary: At the bottom of the heap, packet dispatching relies on hardware-level support for Volatile and CAS
  • Volatile: Using the memory read and write semantics of Volatile and preventing reordering to ensure data visibility
  • CAS: Efficient machine-level atomic instructions borrowed from CAS ensure atomicity of read – change – write operations performed in memory
  • Composition: The use of Volatile variables read/write and CAS to achieve effective communication between threads, ensuring atomicity, visibility, and order

3.3.2 Middle Layer – Basic data structure + algorithm support

  • Overview: In terms of data structure and algorithm design, Doug Lea specifically designed the AQS framework as the concurrency foundation of all concurrency libraries, while introducing non-blocking algorithms and atomic variable classes to enhance concurrency features
  • AQS framework:AQS provides the most basic, efficient concurrency API that Doug Lea expects to be the fundamental solution for all concurrent operations, and most of the implementation in the package relies on AQS (AbstractQueuedSynchronizer), and AQS is underpinned by the underlying support for CAS and Volatile
  • Non-blocking data structure: Non-blocking data structure is the basis of non-blocking queue design, but also an important reference of blocking queue comparison
  • Atomic variable class:Doug Lea designed a library specifically for all atomic variables, and even made alignment enhancements later, such asLongAdder,LongAccumulatorAnd so on, from the side can reflect the importance of numerical operation for programming

3.3.3 High Level – Concurrent class library support

  • Summary: Doug Lea has provided a rich library of concurrency classes in package and make it easy to use concurrency quickly and safely
  • Lock: The Lock interface defines a set of standards for concurrent operations. For details, see the @lock Interface article (version 1.8).
  • Synchronizer:The implementation of the synchronizer for each concurrent class depends on AQS(inheritance), for exampleReentrantLockIn theSync; At the same time, the author willConcurrent classesIt falls within the scope of the synchronizer
  • Blocking queue:As the name implies, queues that support blocking are mainly based onQueueAt the end of the class
  • Actuators: By actuators, we mean the implementers of tasks, such as thread pools and fork-joins
  • Concurrent container:That is, a container that supports concurrencyCOWAnd in order toConcurrentClasses at the beginning, usually concurrent containers are non-blocking