Java面试——并发编程（四）

并发编程11、ConcurrentHashMap并发11.1、减小锁粒度11.2、ConcurrentHashMap的实现12、Java中的线程调度12.1、抢占式调度12.2、协同式调度12.3、Java线程调度的实现抢占式12.4、线程让出CPU的情况13、进程调度算法13.1、优先调度算法13.1.1、先来先服务调度算法13.1.2、短作业优先调度算法13.2、高优先权优先调度算法13.2.1、非抢占式优先调度算法13.2.2、抢占式优先调度算法13.2.3、高响应比优先调度算法13.3、时间片的轮转调度算法13.3.1、时间片轮转法13.3.2、多级反馈队列调度算法14、什么是CAS14.1、CAS的概念比较并交换14.2、CAS的特性乐观锁14.3、CAS自旋等待15、ABA问题16、什么是AQS16.1、AQS的原理16.2、state状态16.3、AQS共享资源的方式独占式和共享式11、ConcurrentHashMap并发ConcurrentHashMap和HashMap的实现方式类似不同的是它采用分段锁的思想支持并发操作所以是线程安全的。下面介绍ConcurrentHashMap是如何采用分段锁的思想来实现多线程并发下的数据安全的。11.1、减小锁粒度减小锁粒度指通过缩小锁定对象的范围来减少锁冲突的可能性最终提高系统的并发能力。减小锁粒度是一种削弱多线程锁竞争的有效方法ConcurrentHashMap并发下的安全机制就是基于该方法实现的。ConcurrentHashMap是线程安全的Map对于HashMap而言最重要的方法是get和set方法如果为了线程安全对整个HashMap加锁则可以得到线程安全的对象但是加锁粒度太大意味着同时只能有一个线程操作HashMap在效率上就会大打折扣而ConcurrentHashMap在内部使用多个Segment在操作数据时会给每个Segment都加锁这样就通过减小锁粒度提高了并发度。11.2、ConcurrentHashMap的实现ConcurrentHashMap在内部细分为若干个小的HashMap叫作数据段Segment​。在默认情况下一个ConcurrentHashMap被细分为16个数据段对每个数据段的数据都单独进行加锁操作。Segment的个数为锁的并发度。ConcurrentHashMap是由Segment数组和HashEntry数组组成的。Segment继承了可重入锁ReentrantLock​它在ConcurrentHashMap里扮演锁的角色。HashEntry则用于存储键值对数据。在每一个ConcurrentHashMap里都包含一个Segment数组Segment的结构和HashMap类似是数组和链表结构。在每个Segment里都包含一个HashEntry数组每个HashEntry都是一个链表结构的数据每个Segment都守护一个HashEntry数组里的元素在对HashEntry数组的数据进行修改时必须首先获得它对应的Segment锁。在操作ConcurrentHashMap时如果需要在其中添加一个新的数据则并不是将整个HashMap加锁而是先根据HashCode查询该数据应该被存放在哪个段然后对该段加锁并完成put操作。在多线程环境下如果多个线程同时进行put操作则只要加入的数据被存放在不同的段中在线程间就可以做到并行的线程安全。12、Java中的线程调度12.1、抢占式调度抢占式调度指每个线程都以抢占的方式获取CPU资源并快速执行在执行完毕后立刻释放CPU资源具体哪些线程能抢占到CPU资源由操作系统控制在抢占式调度模式下每个线程对CPU资源的申请地位是相等从概率上讲每个线程都有机会获得同样的CPU执行时间片并发执行。抢占式调度适用于多线程并发执行的情况在这种机制下一个线程的堵塞不会导致整个进程性能下降。具体流程如图所示。12.2、协同式调度协同式调度指某一个线程在执行完后主动通知操作系统将CPU资源切换到另一个线程上执行。线程对CPU的持有时间由线程自身控制线程切换更加透明更适合多个线程交替执行某些任务的情况。协同式调度有一个缺点如果其中一个线程因为外部原因可能是磁盘I/O阻塞、网络I/O阻塞、请求数据库等待运行阻塞那么可能导致整个系统阻塞甚至崩溃。具体流程如图所示。12.3、Java线程调度的实现抢占式Java采用抢占式调度的方式实现内部的线程调度Java会为每个线程都按照优先级高低分配不同的CPU时间片且优先级高的线程优先执行。优先级低的线程只是获取CPU时间片的优先级被降低但不会永久分配不到CPU时间片。Java的线程调度在保障效率的前提下尽可能保障线程调度的公平性。12.4、线程让出CPU的情况线程让出CPU的情况如下。当前运行的线程主动放弃CPU例如运行中的线程调用yield()放弃CPU的使用权。当前运行的线程进入阻塞状态例如调用文件读取I/O操作、锁等待、Socket等待。当前线程运行结束即运行完run()里面的任务。13、进程调度算法进程调度算法包括优先调度算法、高优先权优先调度算法和基于时间片的轮转调度算法。其中优先调度算法分为先来先服务调度算法和短作业优先调度算法高优先权优先调度算法分为非抢占式优先权算法、抢占式优先权调度算法和高响应比优先调度算法。基于时间片的轮转调度算法分为时间片轮转算法和多级反馈队列调度算法。13.1、优先调度算法优先调度算法包含先来先服务调度算法和短作业进程优先调度算法。13.1.1、先来先服务调度算法先来先服务调度算法指每次调度时都从队列中选择一个或多个最早进入该队列的作业为其分配资源、创建进程和放入就绪队列。调度算法在获取到可用的CPU资源时会从就绪队列中选择一个最早进入队列的进程为其分配CPU资源并运行。该算法优先运行最早进入的任务实现简单且相对公平。13.1.2、短作业优先调度算法短作业优先调度算法指每次调度时都从队列中选择一个或若干个预估运行时间最短的作业为其分配资源、创建进程和放入就绪队列。调度算法在获取到可用的CPU资源时会从就绪队列中选出一个预估运行时间最短的进程为其分配CPU资源并运行。该算法优先运行短时间作业以提高CPU整体的利用率和系统运行效率某些大任务可能会出现长时间得不到调度的情况。13.2、高优先权优先调度算法高优先权优先调度算法在定义任务的时候为每个任务都设置不同的优先权在进行任务调度时优先权最高的任务首先被调度这样资源的分配将更加灵活具体包含非抢占式优先调度算法、抢占式优先调度算法和高响应比优先调度算法。13.2.1、非抢占式优先调度算法非抢占式优先调度算法在每次调度时都从队列中选择一个或多个优先权最高的作业为其分配资源、创建进程和放入就绪队列。调度算法在获取到可用的CPU资源时会从就绪队列中选出一个优先权最高的进程为其分配CPU资源并运行。进程在运行过程中一直持有该CPU直到进程执行完毕或发生异常而放弃该CPU。该算法优先运行优先权高的作业且一旦将CPU分配给某个进程就不会主动回收CPU资源直到任务主动放弃。13.2.2、抢占式优先调度算法抢占式优先调度算法首先把CPU资源分配给优先权最高的任务并运行但如果在运行过程中出现比当前运行任务优先权更高的任务调度算法就会暂停运行该任务并回收CPU资源为其分配新的优先权更高的任务。该算法真正保障了CPU在整个运行过程中完全按照任务的优先权分配资源这样如果临时有紧急作业则也可以保障其第一时间被执行。13.2.3、高响应比优先调度算法高响应比优先调度算法使用了动态优先权的概念即任务的执行时间越短其优先权越高任务的等待时间越长优先权越高这样既保障了快速、并发地执行短作业也保障了优先权低但长时间等待的任务也有被调度的可能性。该优先权的变化规律如下。在作业的等待时间相同时运行时间越短优先权越高在这种情况下遵循的是短作业优先原则。在作业的运行时间相同时等待时间越长优先权越高在这种情况下遵循的是先来先服务原则。作业的优先权随作业等待时间的增加而不断提高加大了长作业获取CPU资源的可能性。高响应比优先调度算法在保障效率短作业优先能在很大程度上提高CPU的使用率和系统性能的基础上尽可能提高了调度的公平性随着任务等待时间的增加优先权提高遵循了先来先到原则​。13.3、时间片的轮转调度算法时间片的轮转调度算法将CPU资源分成不同的时间片不同的时间片为不同的任务服务具体包括时间片轮转法和多级反馈队列调度算法。13.3.1、时间片轮转法时间片轮转法指按照先来先服务原则从就绪队列中取出一个任务并为该任务分配一定的CPU时间片去运行在进程使用完CPU时间片后由一个时间计时器发出时钟中断请求调度器在收到时钟中断请求信号后停止该进程的运行并将该进程放入就绪队列的队尾然后从就绪队列的队首取出一个任务并为其分配CPU时间片去执行。这样就绪队列中的任务就将轮流获取一定的CPU时间片去运行。13.3.2、多级反馈队列调度算法多级反馈队列调度算法在时间片轮询算法的基础上设置多个就绪队列并为每个就绪队列都设置不同的优先权。队列的优先权越高队列中的任务被分配的时间片就越大。默认第一个队列优先权最高其他次之。多级反馈队列调度算法的调度流程为在系统收到新的任务后首先将其放入第一个就绪队列的队尾按先来先服务调度算法排队等待调度。若该进程在规定的CPU时间片内运行完成或者运行过程中出现错误则退出进程并从系统中移除该任务如果该进程在规定的CPU时间片内未运行完成则将该进程转入第2队列的队尾调度执行如果该进程在第2队列中运行一个CPU时间片后仍未完成则将其放入第3队列以此类推在一个长作业从第1队列依次降到第n队列后在第n队列中便以时间片轮转的方式运行。多级反馈队列调度算法遵循以下原则。仅在第一个队列为空时调度器才调度第2队列中的任务。仅在第1(n-1)队列均为空时调度器才会调度第n队列中的进程。如果处理器正在为第n队列中的某个进程服务此时有新进程进入优先权较高的队列第1(n-1)中的任何一个队列​则此时新进程将抢占正在运行的进程的处理器即调度器停止正在运行的进程并将其放回第 n队列的末尾把处理器分配给新来的高优先权进程。多级反馈调度算法相对来说比较复杂它充分考虑了先来先服务调度算法和时间片轮询算法的优势使得对进程的调度更加合理。14、什么是CAS14.1、CAS的概念比较并交换CASCompare And Swap指比较并交换。CAS算法CAS(V, E, N)包含3个参数V表示要更新的变量E表示预期的值N表示新值。在且仅在V值等于 E值时才会将V值设为 N如果 V值和 E值不同则说明已经有其他线程做了更新当前线程什么都不做。最后CAS返回当前V的真实值。14.2、CAS的特性乐观锁CAS操作采用了乐观锁的思想总是认为自己可以成功完成操作。在有多个线程同时使用CAS操作一个变量时只有一个会胜出并成功更新其余均会失败。失败的线程不会被挂起仅被告知失败并且允许再次尝试当然也允许失败的线程放弃操作。基于这样的原理CAS操作即使没有锁也可以发现其他线程对当前线程的干扰并进行恰当的处理。14.3、CAS自旋等待在JDK的原子包java.util.concurrent.atomic里面提供了一组原子类这些原子类的基本特性就是在多线程环境下在有多个线程同时执行这些类的实例包含的方法时会有排他性。其内部便是基于CAS算法实现的即在某个线程进入方法中执行其中的指令时不会被其他线程打断而别的线程就像自旋锁一样一直等到该方法执行完成才由JVM从等待的队列中选择另一个线程进入。相对于synchronized阻塞算法CAS是非阻塞算法的一种常见实现。由于CPU的切换比CPU指令集的操作更加耗时所以CAS的自旋操作在性能上有了很大的提升。JDK具体的实现源码如下publicclassAtomicIntegerextendsNumberimplementsjava.io.Serializable{privatevolatileintvalue;publicfinalintget(){returnvalue;}publicfinalintgetAndIncrement(){for(;;){//CAS自旋一直尝试直到成功intcurrentget();intnextcurrent1;if(compareAndSet(current,next))returncurrent;}}publicfinalbooleancompareAndSet(intexpect,intupdate){returnunsafe.compareAndSwapInt(this,valueOffset,expect,update);}}在以上代码中getAndIncrement采用了CAS操作每次都从内存中读取数据然后将此数据和加1后的结果进行CAS操作如果成功则返回结果否则重试直到成功为止。15、ABA问题对CAS算法的实现有一个重要的前提需要取出内存中某时刻的数据然后在下一时刻进行比较、替换在这个时间差内可能数据已经发生了变化导致产生ABA问题。ABA问题指第1个线程从内存的V位置取出A这时第2个线程也从内存中取出A并将V位置的数据首先修改为B接着又将V位置的数据修改为A这时第1个线程在进行CAS操作时会发现在内存中仍然是A然后第1个线程操作成功。尽管从第1个线程的角度来说CAS操作是成功的但在该过程中其实V位置的数据发生了变化只是第1个线程没有感知到罢了这在某些应用场景下可能出现过程数据不一致的问题。部分乐观锁是通过版本号version来解决ABA问题的具体的操作是乐观锁每次在执行数据的修改操作时都会带上一个版本号在预期的版本号和数据的版本号一致时就可以执行修改操作并对版本号执行加1操作否则执行失败。因为每次操作的版本号都会随之增加所以不会出现ABA问题因为版本号只会增加不会减少。16、什么是AQSAQSAbstract Queued Synchronizer是一个抽象的队列同步器通过维护一个共享资源状态Volatile IntState和一个先进先出FIFO的线程等待队列来实现一个多线程访问共享资源的同步框架。16.1、AQS的原理AQS为每个共享资源都设置一个共享资源锁线程在需要访问共享资源时首先需要获取共享资源锁如果获取到了共享资源锁便可以在当前线程中使用该共享资源如果获取不到则将该线程放入线程等待队列等待下一次资源调度具体的流程如图所示。许多同步类的实现都依赖于AQS例如常用的ReentrantLock、Semaphore 和CountDownLatch。16.2、state状态Abstract Queued Synchronizer维护了一个volatile int类型的变量用于表示当前的同步状态。Volatile虽然不能保证操作的原子性但是能保证当前变量state的可见性。state的访问方式有三种getState()、setState()和compareAndSetState()均是原子操作其中compareAndSetState的实现依赖于Unsafe的compareAndSwapInt()。具体的JDK代码实现如下//返回共享资源状态此操作的内存语义为volatile修饰的原子读操作protectedfinalintgetState(){returnstate;}//设置共享资源状态此操作的内存语义为volatile修饰的原子写操作protectedfinalvoidsetState(intnewState){statenewState;}//自动将同步状态设置为给定的更新状态值如果当前状态值等于预期值//此操作的内存语义为volatile修饰的原子读写操作protectedfinalbooleancompareAndSetState(intexpect,intupdate){returnunsafe.compareAndSwapInt(this,stateOffset,expect,update);}16.3、AQS共享资源的方式独占式和共享式AQS定义了两种资源共享方式独占式Exclusive和共享式Share​。独占式只有一个线程能执行具体的Java实现有ReentrantLock。共享式多个线程可同时执行具体的Java实现有Semaphore和CountDownLatch。AQS只是一个框架只定义了一个接口具体资源的获取、释放都交由自定义同步器去实现。不同的自定义同步器争用共享资源的方式也不同自定义同步器在实现时只需实现共享资源state的获取与释放方式即可至于具体线程等待队列的维护如获取资源失败入队、唤醒出队等AQS已经在顶层实现好不需要具体的同步器再做处理。自定义同步器的主要方法如表所示。同步器的实现是AQS的核心内存。ReentrantLock对AQS的独占方式实现为ReentrantLock中的state初始值为0时表示无锁状态。在线程执行tryAcquire()获取该锁后ReentrantLock中的state1这时该线程独占ReentrantLock锁其他线程在通过tryAcquire()获取锁时均会失败直到该线程释放锁后state再次为0其他线程才有机会获取该锁。该线程在释放锁之前可以重复获取此锁每获取一次便会执行一次state1因此ReentrantLock也属于可重入锁。但获取多少次锁就要释放多少次锁这样才能保证state最终为0。如果获取锁的次数多于释放锁的次数则会出现该线程一直持有该锁的情况如果获取锁的次数少于释放锁的次数则运行中的程序会报锁异常。CountDownLatch对AQS的共享方式实现为CountDownLatch将任务分为N个子线程去执行将state也初始化为N, N与线程的个数一致N个子线程是并行执行的每个子线程都在执行完成后countDown()一次state会执行CAS操作并减1。在所有子线程都执行完成state0时会unpark()主线程然后主线程会从await()返回继续执行后续的动作。一般来说自定义同步器要么采用独占方式要么采用共享方式实现类只需实现tryAcquire、tryRelease或tryAcquireShared、tryReleaseShared中的一组即可。但AQS也支持自定义同步器同时实现独占和共享两种方式例如ReentrantReadWriteLock在读取时采用了共享方式在写入时采用了独占方式。