• CAS算法-实现原理

    CAS是什么？

        CAS的全称为Compare and swap 比较并交换。CAS又经常被称为乐观锁，主要的三个变量，内存值V，旧的预期值P，需要修改的新值N，原理就是：当 P等于V ，则将 N值赋给 V;

    （个人理解：当你修改密码时，你的旧密码跟你输入的一致才能更换！）

    ‍

    47fe51246647fd26848f5c7af4679043.png

    CAS解决了什么问题？

        解决并发访问中无锁的非阻塞算法的实现。

    CAS存在什么问题？

        ABA问题：添加版本号解决;其实就是乐观锁;

        解决方案:通过添加版本号来解决。

        内存开销大：若并发过大，会导致内存开销很大;

    CAS有哪些应用场景？

        jdk默认自带的Atomick开头的实现类底层都是使用了CAS算法;

        自旋锁的实现，底层也是通过CAS轮询的方式进行实现;

    cas的实现

        存在ABA问题的实现方式:

    1. /**
    2.  * @author: csh
    3.  * @Date: 2022/8/6 21:05
    4.  * @Description: cas工具类 该类存在一个缺陷，没有版本控制会导致aba问题
    5.  */
    6. public class CasV1 {
    7.     //内存的值
    8.     private int value;
    9.     //获取值
    10.     public synchronized int getValue() {
    11.         return value;
    12.     }
    13.  
    14.     //对比值并且设置值
    15.     public synchronized int compareAndSwap(int defaultValue,int newValue){
    16.         int oldValue = value;
    17.         if(oldValue == defaultValue){
    18.             this.value = newValue;
    19.         }
    20.         return oldValue;
    21.     }
    22.  
    23.     //对比值
    24.     public synchronized boolean compareAndSet(int defaultValue,int newValue){
    25.         return defaultValue==compareAndSwap(defaultValue,newValue);
    26.     }
    27. }
    28. }

    验证

    1. /**
    2.  * @author: csh
    3.  * @Date: 2022/8/6 21:03
    4.  * @Description:cas实现验证
    5.  */
    6. public class CasStudy {
    7.     public static void main(String[] args) {
    8.         CasV1 casV1 = new CasV1();
    9.         for (int i = 0; i < 100; i++) {
    10.             new Thread(new Runnable() {
    11.                 @Override
    12.                 public void run() {
    13.                     int defaultValue = casV1.getValue();
    14.                     int newValue = (int) (Math.random() * 10000);
    15.                     boolean setResult = casV1.compareAndSet(defaultValue,newValue );
    16.                     System.out.println("新值："+newValue+"设置结果为：" + setResult);
    17.                 }
    18.             }).start();
    19.         }
    20.     }
    21. }

    结果

    1. 新值：2558设置结果为：true
    2. 新值：6016设置结果为：true
    3. 新值：6498设置结果为：false
    4. 新值：5326设置结果为：false
    5. 新值：9294设置结果为：true
    6. 新值：7897设置结果为：true
    7. 新值：6352设置结果为：true
    8. 新值：8844设置结果为：false
    9. 新值：1935设置结果为：true
    10. 新值：1502设置结果为：false
    11. 新值：8283设置结果为：false
    12. 新值：943设置结果为：true
    13. 新值：1600设置结果为：false
    14. 新值：7259设置结果为：true
    15. 新值：8898设置结果为：false
    16. 新值：9597设置结果为：false
    17. 新值：8883设置结果为：true
    18. 新值：4458设置结果为：true
    19. 新值：7120设置结果为：true
    20. 新值：5546设置结果为：false
    21. 新值：2138设置结果为：true
    22. 新值：8985设置结果为：false
    23. 新值：5666设置结果为：true
    24. 新值：3799设置结果为：false
    25. 新值：2267设置结果为：true
    26. 新值：1585设置结果为：false
    27. 新值：4961设置结果为：false
    28. 新值：9770设置结果为：false
    29. 新值：4449设置结果为：true
    30. 新值：4370设置结果为：true
    31. 新值：7385设置结果为：true
    32. 新值：9800设置结果为：true
    33. 新值：7130设置结果为：true
    34. 新值：7106设置结果为：true
    35. 新值：8088设置结果为：true
    36. 新值：894设置结果为：false
    37. 新值：639设置结果为：true
    38. 新值：7351设置结果为：true
    39. 新值：1438设置结果为：true
    40. 新值：2947设置结果为：true
    41. 新值：9486设置结果为：true
    42. 新值：845设置结果为：true
    43. 新值：7280设置结果为：true
    44. 新值：664设置结果为：true
    45. 新值：1971设置结果为：true
    46. 新值：6174设置结果为：true
    47. 新值：3707设置结果为：true
    48. 新值：8093设置结果为：true
    49. 新值：3523设置结果为：true
    50. 新值：8760设置结果为：true
    51. 新值：5516设置结果为：true
    52. 新值：4813设置结果为：true
    53. 新值：9809设置结果为：true
    54. 新值：6009设置结果为：true
    55. 新值：9110设置结果为：true
    56. 新值：4006设置结果为：true
    57. 新值：5954设置结果为：true
    58. 新值：4544设置结果为：true
    59. 新值：3239设置结果为：true
    60. 新值：7333设置结果为：true
    61. 新值：3658设置结果为：true
    62. 新值：5678设置结果为：true
    63. 新值：3892设置结果为：true
    64. 新值：1269设置结果为：true
    65. 新值：139设置结果为：true
    66. 新值：5508设置结果为：true
    67. 新值：4191设置结果为：true
    68. 新值：2466设置结果为：true
    69. 新值：319设置结果为：true
    70. 新值：1743设置结果为：true
    71. 新值：9549设置结果为：true
    72. 新值：75设置结果为：true
    73. 新值：4112设置结果为：true
    74. 新值：334设置结果为：true
    75. 新值：5523设置结果为：true
    76. 新值：3719设置结果为：true
    77. 新值：2367设置结果为：true
    78. 新值：2669设置结果为：true
    79. 新值：819设置结果为：true
    80. 新值：6787设置结果为：true
    81. 新值：2509设置结果为：true
    82. 新值：4291设置结果为：true
    83. 新值：735设置结果为：true
    84. 新值：6104设置结果为：true
    85. 新值：354设置结果为：true
    86. 新值：6324设置结果为：true
    87. 新值：6938设置结果为：true
    88. 新值：630设置结果为：true
    89. 新值：2881设置结果为：true
    90. 新值：6367设置结果为：true
    91. 新值：7941设置结果为：true
    92. 新值：3855设置结果为：true
    93. 新值：7853设置结果为：true
    94. 新值：6457设置结果为：true
    95. 新值：901设置结果为：true
    96. 新值：6800设置结果为：true
    97. 新值：9424设置结果为：true
    98. 新值：1911设置结果为：true
    99. 新值：1131设置结果为：true
    100. 新值：91设置结果为：true

    解决ABA问题的版本。

    1. package com.hong.arithmetic.cas;
    2.  
    3. import java.util.concurrent.atomic.AtomicReference;
    4.  
    5. /**
    6.  * @author: csh
    7.  * @Date: 2022/8/6 21:05
    8.  * @Description: cas工具类 通过jdk自带AtomicReference 实现
    9.  */
    10. public class CasV2 {
    11.  
    12.     public CasV2() {
    13.     }
    14.  
    15.     public CasV2(AtomicReference value) {
    16.         this.value = value;
    17.     }
    18.  
    19.     //内存的值
    20.     AtomicReference value;
    21.  
    22.     //获取值
    23.     public Integer getValue() {
    24.         return value.get();
    25.     }
    26.  
    27.     //对比值
    28.     public boolean compareAndSet(int defaultValue, int newValue) {
    29.         return value.compareAndSet(defaultValue, newValue);
    30.     }
    31.  
    32.  
    33. }

    运行

    1. //解决ABA问题的版本
    2. CasV2 casV2 = new CasV2(new AtomicReference<>(10));
    3. for (int i = 0; i < 100; i++) {
    4.     new Thread(new Runnable() {
    5.         @Override
    6.         public void run() {
    7.             int defaultValue = casV2.getValue();
    8.             int newValue = (int) (Math.random() * 10000);
    9.             boolean setResult = casV2.compareAndSet(defaultValue,newValue );
    10.             System.out.println("ABA版本新值："+newValue+"设置结果为：" + setResult);
    11.         }
    12.     },"ABA").start();
    13. }

    结果

    1. ABA版本新值：8648设置结果为：false
    2. ABA版本新值：1194设置结果为：false
    3. ABA版本新值：7614设置结果为：false
    4. ABA版本新值：2322设置结果为：false
    5. ABA版本新值：7366设置结果为：true
    6. ABA版本新值：1427设置结果为：false
    7. ABA版本新值：2877设置结果为：false
    8. ABA版本新值：5098设置结果为：false
    9. ABA版本新值：1592设置结果为：false
    10. ABA版本新值：2739设置结果为：false
    11. ABA版本新值：1654设置结果为：false
    12. ABA版本新值：8171设置结果为：false
    13. ABA版本新值：2893设置结果为：false
    14. ABA版本新值：3774设置结果为：false
    15. ABA版本新值：8768设置结果为：false
    16. ABA版本新值：3924设置结果为：false
    17. ABA版本新值：397设置结果为：false
    18. ABA版本新值：6727设置结果为：false
    19. ABA版本新值：1518设置结果为：false
    20. ABA版本新值：2734设置结果为：false
    21. ABA版本新值：5193设置结果为：false
    22. ABA版本新值：9006设置结果为：false
    23. ABA版本新值：2832设置结果为：false
    24. ABA版本新值：1447设置结果为：false
    25. ABA版本新值：2595设置结果为：false
    26. ABA版本新值：1559设置结果为：false
    27. ABA版本新值：3129设置结果为：false
    28. ABA版本新值：2254设置结果为：false
    29. ABA版本新值：420设置结果为：false
    30. ABA版本新值：2362设置结果为：false
    31. ABA版本新值：3229设置结果为：false
    32. ABA版本新值：4724设置结果为：false
    33. ABA版本新值：5974设置结果为：false
    34. ABA版本新值：4991设置结果为：false
    35. ABA版本新值：1195设置结果为：false
    36. ABA版本新值：4314设置结果为：false
    37. ABA版本新值：9551设置结果为：false
    38. ABA版本新值：1287设置结果为：false
    39. ABA版本新值：4683设置结果为：false
    40. ABA版本新值：1418设置结果为：false
    41. ABA版本新值：3393设置结果为：false
    42. ABA版本新值：7038设置结果为：false
    43. ABA版本新值：7149设置结果为：false
    44. ABA版本新值：5323设置结果为：false
    45. ABA版本新值：3281设置结果为：false
    46. ABA版本新值：5904设置结果为：false
    47. ABA版本新值：8933设置结果为：false
    48. ABA版本新值：5726设置结果为：false
    49. ABA版本新值：8065设置结果为：false
    50. ABA版本新值：5671设置结果为：false
    51. ABA版本新值：2667设置结果为：false
    52. ABA版本新值：1780设置结果为：false
    53. ABA版本新值：9494设置结果为：false
    54. ABA版本新值：664设置结果为：false
    55. ABA版本新值：264设置结果为：false
    56. ABA版本新值：7175设置结果为：false
    57. ABA版本新值：3667设置结果为：false
    58. ABA版本新值：8690设置结果为：false
    59. ABA版本新值：3084设置结果为：false
    60. ABA版本新值：3851设置结果为：false
    61. ABA版本新值：1720设置结果为：false
    62. ABA版本新值：9836设置结果为：false
    63. ABA版本新值：4408设置结果为：false
    64. ABA版本新值：308设置结果为：false
    65. ABA版本新值：1583设置结果为：false
    66. ABA版本新值：5942设置结果为：false
    67. ABA版本新值：8630设置结果为：false
    68. ABA版本新值：4310设置结果为：false
    69. ABA版本新值：502设置结果为：false
    70. ABA版本新值：1471设置结果为：false
    71. ABA版本新值：6506设置结果为：false
    72. ABA版本新值：5214设置结果为：false
    73. ABA版本新值：9084设置结果为：false
    74. ABA版本新值：4223设置结果为：false
    75. ABA版本新值：2937设置结果为：false
    76. ABA版本新值：2837设置结果为：false
    77. ABA版本新值：4354设置结果为：false
    78. ABA版本新值：811设置结果为：false
    79. ABA版本新值：7374设置结果为：false
    80. ABA版本新值：125设置结果为：false
    81. ABA版本新值：8256设置结果为：false
    82. ABA版本新值：9112设置结果为：false
    83. ABA版本新值：9827设置结果为：false
    84. ABA版本新值：8817设置结果为：false
    85. ABA版本新值：1897设置结果为：false
    86. ABA版本新值：3784设置结果为：false
    87. ABA版本新值：1233设置结果为：false
    88. ABA版本新值：1902设置结果为：false
    89. ABA版本新值：7025设置结果为：false
    90. ABA版本新值：5885设置结果为：false
    91. ABA版本新值：5254设置结果为：false
    92. ABA版本新值：4337设置结果为：false
    93. ABA版本新值：9677设置结果为：false
    94. ABA版本新值：1991设置结果为：false
    95. ABA版本新值：7234设置结果为：false
    96. ABA版本新值：1155设置结果为：false
    97. ABA版本新值：861设置结果为：false
    98. ABA版本新值：9570设置结果为：false
    99. ABA版本新值：9935设置结果为：false
    100. ABA版本新值：1030设置结果为：false

    可以看到只有一个成功，所以底层可以通过while循环方式进行重新获取最新进行判断。

    看看jdkAtomicInteger底层的实现

    1. //这里底层通过 unsafe来实现，这个是由c++来写的所以看不到。
    2. public final boolean compareAndSet(int expect, int update) {
    3.     return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
    4. }

    但是可以通过其他方法发现，很多都是通过先获取当前值，然后去判断是否设置成功，如果没成功通过轮训方式进行设置，直到成功为止，所以用这个CAS会导致cpu飙高的原因就在这里。

    1. public final int getAndUpdate(IntUnaryOperator updateFunction) {
    2.     int prev, next;
    3.     do {
    4.         prev = get();
    5.         next = updateFunction.applyAsInt(prev);
    6.     } while (!compareAndSet(prev, next));
    7.     return prev;
    8. }

    最后

        cas在算法在很多一些基础的开发都会用到，只是现在Jdk默认有Atomic这个包，通过这个包已经为我们实现了功能，我们可以很方便引用已封装好的包进行实现，本文主要讲解原理。不过在使用cas上面有一点需要特别注意，因为cas如果很多处同时在包循环会导致cpu飙高，所以这点特别重要，一些公司有cpu监控的，要特别注意，避免频繁告警或者因为原来已经很高的cpu导致打到100%，那就很可能引发事故。

  • 相关阅读:
    C#实现本地服务器多客户端同频道通信
    oracle定时任务的使用
    时序数据库-5-[IoTDB]的数据迁移
    2022-11-18 mysql-filesort-分析
    SQL优化之深分页
    Python是什么？要如何学习？
    『华强买瓜』奇袭好莱坞！Jupyter也能创建可交互仪表板啦！超全面的英语论文写作套路；神经辐射场NeRF工具包；前沿论文 | ShowMeAI资讯日报
    微信答题小程序产品研发-系统架构设计
    索尼 toio™ 应用创意开发征文互动小企鹅
    网站源码备份 [极客大挑战 2019]PHP1
  • 原文地址：https://blog.csdn.net/qq_16498553/article/details/126204119