并发编程-基础

冷不防 2023-02-28 01:37 56阅读 0赞

# 并发基础 #

## 一，进程和线程 ##

### 1.1 进程和线程的定义 ###

*  进程是程序的一次执行过程，程序是静态的，进程是动态的
 *  线程是一个比进程更小的执行单位，一个进程在执行过程中可以产生很多线程，每个线程都有自己独立的程序计数器，栈，也可以共享进程内的堆和方法区，进程之前的切换开销比线程大

### 1.2 进程和线程的关系，区别 ###

**关系**

*  操作系统内存中可以存在多个进程，让操作系统并发成为了可能
 *  线程在进程内可以存在多个，同时处理多个进程子任务，让进程内部并发成为了可能

**区别：**

*  进程拥有独立的内存地址空间，进程和进程之间的内存地址空间是分隔开的，数据也是独立的，各个进程间互不打扰，线程共享进程内的地址空间和数据
 *  进程单独占有一定的内存地址空间，一个进程出现问题不会影响其他进程，不影响主程序的稳定性，可靠性高；一个线程崩溃可能影响整个程序的稳定性，可靠性较低。
 *  进程是操作系统资源分配的基本单位，线程是CPU调度的最小单位
 *  进程上下文切换消耗比线程大

### 1.3 状态转换 ###

**线程和进程的基本状态转换图：**

![SouthEast][]

**java线程状态转换图：**

![format_png][]

区别：java中的runnable包括就绪和运行中

### 1.4 进程调度算法 ###

**时间片轮转**

*  每个进程分配一个固定的时间片大小，时间片执行完则让出CPU资源，CPU执行下一个进程

**优先级调度**

*  非抢占式优先权算法
    
     *  在这种方式下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成
 *  抢占式优先权算法
    
     *  在这种方式下，系统同样是把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程

**先来先服务**

*  利用就绪队列实现，每次都是队列头部的进程获得调度，调度完成后进入队列尾部

**多级反馈队列**

*  被公认的一种较好的进程调度算法，总和了多种调度算法
 *  有多个优先级队列，从高到低，优先级越高的队列，时间片越短
 *  当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……，如此下去，当一个长作业(进程)从第一队列依次降到第n队列后，在第n队列便采取按时间片轮转的方式运行。
 *  仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第1～(i-1)队列均空时，才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列(第1～(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机，即第i队列中某个正在运行的进程的时间片用完后，由调度程序选择优先权较高的队列中的那一个进程，把处理机分配给它。

## 二，CAS和原子操作 ##

### 2.1 乐观锁和悲观锁 ###

**乐观锁**

每次进入临界区时都认为不会发生冲突，无需加锁

乐观锁通常是使用CAS去保证线程安全

**悲观锁**

每次进入临界区都认为会发生冲突，每次都加锁，常用手段：synchronized，lock

### 2.2 CAS ###

CAS的全称是：比较并交换（Compare And Swap）。在CAS中，有这样三个值：

*  V：要更新的变量(var)
 *  E：预期值(expected)
 *  N：新值(new)

**过程：**

判断要更新的变量V是否等于E，等于则将V更新为新值N，不等于则什么都不干

他的底层是CPU的原子指令cmpxchg，从CPU级别保证原子性

当多个线程同时使用CAS操作一个变量时，只有一个会胜出，并成功更新，其余均会失败，但失败的线程并不会被挂起，仅是被告知失败，并且允许再次尝试，当然也允许失败的线程放弃操作

**Java中的CAS**

java中通过unsafe类实现了CAS和一些内存的直接操作

boolean compareAndSwapObject(Object o, long offset,Object expected, Object x);
    boolean compareAndSwapInt(Object o, long offset,int expected,int x);
    boolean compareAndSwapLong(Object o, long offset,long expected,long x);

Java中的原子类封装了unsafe类中实现的CAS，在java.util.concurrent.atomic包下面

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YAPaurht-1595093828582)(https://gblobscdn.gitbook.com/assets%2F-L\_5HvtIhTFW9TQlOF8e%2F-L\_5TIKcBFHWPtY3OwUo%2F-L\_5TJH5r93uLYB5jEEg%2F%E5%8E%9F%E5%AD%90%E7%B1%BB.jpg?alt=media)\]

**源码分析：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70]

具体的CAS方法：

// 只暴露两个参数：value的旧值和新值
        public final boolean compareAndSet(int expect, int update) {
        
            return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
        }

可以看到内部走的是unsafe的cas方法

public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

再看底层unsafe类顶底层cpp：

UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSwapInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x))
      UnsafeWrapper("Unsafe_CompareAndSwapInt");
      oop p = JNIHandles::resolve(obj);
      // 根据偏移量，计算 value 的地址。这里的 offset 就是 AtomaicInteger 中的 valueOffset
      jint* addr = (jint *) index_oop_from_field_offset_long(p, offset);
      // 调用 Atomic 中的函数 cmpxchg，该函数声明于 Atomic.hpp 中
      return (jint)(Atomic::cmpxchg(x, addr, e)) == e;
    UNSAFE_END

内部走的是：

(jint)(Atomic::cmpxchg(x, addr, e)) == e;

如果更新为新值e则CAS成功，再看底层该cmpxchg方法：

// atomic_windows_x86.inline.hpp
    #define LOCK_IF_MP(mp) __asm cmp mp, 0  \
                           __asm je L0      \
                           __asm _emit 0xF0 \
                           __asm L0:
                
    inline jint Atomic::cmpxchg (jint exchange_value, volatile jint* dest, jint compare_value) {
      // alternative for InterlockedCompareExchange
      int mp = os::is_MP();
      __asm {
        mov edx, dest
        mov ecx, exchange_value
        mov eax, compare_value
        LOCK_IF_MP(mp)
        cmpxchg dword ptr [edx], ecx
      }
    }

用到的汇编指令是：

cmpxchg dword ptr [edx], ecx

**CAS的缺陷**

ABA问题：

> ABA问题：就是一个值原来是A，变成了B，又变回了A。这个时候使用CAS是检查不出变化的，但实际上却被更新了两次。

解决方法：加版本号或者时间戳判断

从JDK 1.5开始，JDK的atomic包里提供了一个类AtomicStampedReference类来解决ABA问题。

**AtomicStampedReference是如何解决ABA问题**

AtomicStampedReference将对象引用和版本戳封装成一个pair

private static class Pair<T> {
        
        final T reference;
        final int stamp;
        private Pair(T reference, int stamp) {
        
            this.reference = reference;
            this.stamp = stamp;
        }
        static <T> Pair<T> of(T reference, int stamp) {
        
            return new Pair<T>(reference, stamp);
        }
    }

使用该atomicStampedReference时，传入需要cas更新的对于引用和版本戳即可

public AtomicStampedReference(V initialRef, int initialStamp) {
        
        pair = Pair.of(initialRef, initialStamp);
    }

CAS流程分析：检查当前引用是否等于预期引用，并且检查当前标志是否等于预期标志，如果二者都相等，才使用CAS设置为新的值和标志

public boolean compareAndSet(V   expectedReference,
                                 V   newReference,
                                 int expectedStamp,
                                 int newStamp) {
        
        Pair<V> current = pair;
        return
            expectedReference == current.reference &&
            expectedStamp == current.stamp &&
            ((newReference == current.reference &&
              newStamp == current.stamp) ||
             casPair(current, Pair.of(newReference, newStamp)));
    }
        
    private boolean casPair(Pair<V> cmp, Pair<V> val) {
        
        return UNSAFE.compareAndSwapObject(this, pairOffset, cmp, val);
    }

*  CAS多与自旋结合。如果自旋CAS长时间不成功，会占用大量的CPU资源。pause指令
 *  只能保证一个共享变量的原子操作,使用JDK 1.5开始就提供的AtomicReference类保证对象之间的原子性，把多个变量放到一个对象里面进行CAS操作；

[SouthEast]: /images/20230209/e2486d17346b4e34b9eea1e5e99d38d9.png
[format_png]: /images/20230209/7fc2d3ba9d5e493d8f9faab74e877852.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70]: /images/20230209/6feb0c1104334ca29f9c08cd71c6f1a8.png