[面试直通版]操作系统之锁、同步与通信(下)

点击->操作系统复习的文章集<-点击

目录

CAS原理与无锁技术

典型问题：

大量使用锁的弊端

无锁技术的基石：CAS技术

CAS与无锁队列

CAS与ABA问题

分布式锁实现

典型问题：

分布式锁场景分析：秒杀系统-库存超卖

分布式锁场景

分布式锁的实现

---

• CAS原理与无锁技术

• 典型问题：

• 请简述无锁数据结构的原理
• CAS是什么？请简述对CAS的理解

• 大量使用锁的弊端

• 开发难度：并行系统访问临界资源必须考虑加锁
• 墨菲定律：只要存在的一定会发生，死锁
• 调度问题：低优先级线程持有锁导致高优先级线程无法执行
• 性能问题：满足一致性要求的前提下需要串行访问
• 锁粒度：锁粒度过小/过大，过小则死锁概率增加，过大又会产生性能问题，设计不当

• 无锁技术的基石：CAS技术

• 回顾原子性：
• 原子性是指一系列操作不可被中断的特性；
• 这一系列操作要么全部执行完成，要么全部没有执行，不存在部分执行，部分未执行的情况
• CAS本质是原子性的CPU指令
• CAS—Compare & Set，或是 Compare & Swap，现在几乎所有的CPU指令都支持CAS的原子操作，X86下对应的是 CMPXCHG 汇编指令
• 做2工作：比较旧值和交换新值
• 除了CAS还有一些类似的命令：
• Fetch And Add：
• 一般用来对变量做＋1的原子操作
• Test And Set：
• 写值到某个内存位置并传回其旧值

• CAS与无锁队列

• 来个例子：
• 一个队列，有8个元素，其内为1-8，队尾元素为8
• 在并发的场景下对队列添加一个元素9时
• 因为在并发的环境下执行
• 在添加元素9时，有可能有别的线程在添加10，或更多的线程添加11,12等等
• 为使队列是正确添加的，就需要给队列添加一个锁，这时队列就相当于是一个临界资源
• 先加锁->更新新尾部值->释放锁
• 是一个串行的操作
• 通过这个锁可以使并发的添加改成串行的访问
• 那么无锁数据结构是怎么使用CAS来解决这一问题的呢
• CAS操作，不锁队列
• 当前push是失败的话，就循环重试，直至成功
• 取到的队列尾部与旧的尾部不一样时就会失败
• 并发场景下，如果CAS执行失败，则说明此时此刻有其他线程正在插入数据
• 而如果CAS执行成功，则说明当前线程插入成功

• CAS与ABA问题

• ABA问题是指CAS交换数据在多次操作后恢复原值而线程无法感知的问题
• 来个例子：
• 还是一个队列，有8个元素，其内为1-8，队尾元素为8，要添加元素9
• A：要添加9，尾部还是8
• B：9已添加，尾部是9
• A：将9弹出，复原尾部是8
• 而CAS判断成功与否的关键是判断旧值与当前取出值是否是同一值
• 当前线程以为的旧值：8
• 实际的旧值：8->9->8
• 当前线程认为CAS成功了，实际上当前tail已经被修改多次
• 解决：
• 给旧值一个版本号的概念，进行操作后版本号就不一样了
• 通过对比值以及版本号就可以唯一的确定和之前是否一样

• 分布式锁实现

• 典型问题：

• 请简述项目中分布式锁的实现方式
• 你了解业界哪些分布式锁框架

• 分布式锁场景分析：秒杀系统-库存超卖

• 后台系统因为要应对瞬时并发量很大的用户请求
• 所以后台系统它可能是多节点无状态的去部署的
• 而Redis和MySQL就通过热冷分离的方式去保存不同类型的数据
• 对于需要秒杀的库存，通常都是保存在Redis
• 这时Redis里的库存数据就相当于是系统里面的临界资源
• 后台系统就相当于是多个线程或多个进程，同时地需要访问这个临界资源
• 此时就需要一个分布式锁来保护临界资源

• 分布式锁场景

• 分布式部署：集群、微服务
• 服务节点之间需要通信
• 数据强一致性要求、性能要求、并发量要求
• 例：订单系统，秒杀系统
• 积分系统，消费系统
• 消息中间件，服务中间件，数据发布-订阅

• 分布式锁的实现

• 基于Redis
• Redis是一个使用ANSI C编写的开源、支持网络、基于内存、分布式、可选持久性的键值对存储数据库
• 它读写性能优异
• 内存读写，可持久化数据
• 数据类型丰富，单线程、数据自动过期、发布-订阅
• setnx
• del
• 但它有单点问题，容易引起雪崩效应
• 所以对于Redis实现的分布式锁一般是使用Redis集群来实现的
• 它可以避免单点问题
• 节点一致性由集群保证
• 基于Zookeeper
• Zookeeper是一个分布式的，开放源码的分布式应用程序协调服务，是Google的Chubby一个开源的实现，是Hadoop和Hbase的重要组件
• 它是一个为分布式应用提供一致性服务的软件
• 提供的功能包括：配置维护、域名服务、分布式同步、组服务等
• Zookeeper数据节点：znode
• 服务1在Zookeeper创建znode1
• 服务2在Zookeeper创建znode1失败
• 服务1释放znode，服务2创建成功
• 临时节点：临时节点由某个客户端创建，当客户端与ZK集群断开连接，则该节点自动被删除
• 基于传统数据库：MySQL
• MySQL提供一致性服务：事务、表级锁、行级锁
• UNIQUE KEY：表级唯一，不能重复插入
• 通过MySQL保证同一个KEY只有一个节点能插入成功
• 通过删除记录释放锁
• 把锁竞争的压力交给了MySQL，且MySQL同样存在单点问题，需要集群解决