// 偏向锁获取流程（JVM源码简化）
class BiasedLocking {
    // 1. 检查是否可偏向
    if (!mark.is_biased_anonymously()) {
        // 2. 检查线程ID是否匹配
        if (mark.thread() == current_thread) {
            // 3. 已持有偏向锁，直接进入
            return true;
        }
    }
    // 4. CAS设置线程ID
    if (CAS(mark.word(), expected, current_thread_id)) {
        return true;  // 偏向成功
    }
    // 5. 偏向失败，撤销偏向锁
    revoke_bias();
}

// 轻量级锁加锁流程
class LightweightLock {
    void lock(Object obj) {
        // 1. 在栈帧中创建 Lock Record
        LockRecord record = new LockRecord();
        record.displaced_header = obj.mark_word();
        
        // 2. CAS替换对象头
        if (CAS(obj.mark_word(), record.displaced_header, record.ptr())) {
            return;  // 加锁成功
        }
        
        // 3. 自旋重试（JDK 6+ 自适应自旋）
        int spin_count = 0;
        while (spin_count < MAX_SPIN) {
            if (CAS(obj.mark_word(), record.displaced_header, record.ptr())) {
                return;
            }
            spin_count++;
        }
        
        // 4. 自旋失败，膨胀为重量级锁
        inflate_to_heavyweight(obj);
    }
}

// Monitor 对象结构（HotSpot源码）
class ObjectMonitor {
    ObjectWaiter* _wait_set;      // 等待队列（调用wait()）
    ObjectWaiter* _entry_list;    // 阻塞队列（等待获取锁）
    Thread* _owner;               // 当前持有锁的线程
    int _count;                   // 重入次数
    volatile int _recursions;     // 递归计数
    
    void enter(Thread* self) {
        // 1. CAS尝试获取
        if (CAS(&_owner, NULL, self)) {
            return;
        }
        
        // 2. 重入检查
        if (_owner == self) {
            _recursions++;
            return;
        }
        
        // 3. 自旋尝试
        if (TrySpin(self)) {
            return;
        }
        
        // 4. 加入阻塞队列，挂起线程
        ParkEvent* event = self->_ParkEvent;
        _entry_list.enqueue(self);
        event->park();  // 系统调用，线程挂起
    }
}

public abstract class AbstractQueuedSynchronizer extends AbstractOwnableSynchronizer {
    
    // 状态变量（volatile保证可见性）
    private volatile int state;
    
    // 等待队列头节点
    private transient volatile Node head;
    
    // 等待队列尾节点
    private transient volatile Node tail;
    
    // Node 结构
    static final class Node {
        static final Node SHARED = new Node();      // 共享模式
        static final Node EXCLUSIVE = null;         // 独占模式
        
        volatile int waitStatus;  // 节点状态
        volatile Node prev;       // 前驱节点
        volatile Node next;       // 后继节点
        volatile Thread thread;   // 等待的线程
        Node nextWaiter;          // 条件队列下一个节点
        
        // waitStatus 常量
        static final int CANCELLED =  1;   // 线程已取消
        static final int SIGNAL    = -1;   // 后继节点需要唤醒
        static final int CONDITION = -2;   // 在条件队列中等待
        static final int PROPAGATE = -3;   // 共享模式下传播
    }
}

// AQS.acquire() 完整流程
public final void acquire(int arg) {
    // 1. 尝试获取锁（子类实现）
    if (!tryAcquire(arg) &&
        // 2. 获取失败，加入等待队列
        acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
        // 3. 处理中断
        selfInterrupt();
}

// addWaiter: 添加节点到队尾
private Node addWaiter(Node mode) {
    Node node = new Node(mode);
    
    // 快速尝试入队
    Node oldTail = tail;
    if (oldTail != null) {
        node.prev = oldTail;
        if (compareAndSetTail(oldTail, node)) {
            oldTail.next = node;
            return node;
        }
    }
    
    // 自旋入队
    enq(node);
    return node;
}

// acquireQueued: 在队列中自旋等待
final boolean acquireQueued(final Node node, int arg) {
    boolean failed = true;
    try {
        boolean interrupted = false;
        for (;;) {
            final Node p = node.predecessor();
            
            // 前驱是头节点，尝试获取锁
            if (p == head && tryAcquire(arg)) {
                setHead(node);  // 获取成功，设为头节点
                p.next = null;  // 帮助GC
                failed = false;
                return interrupted;
            }
            
            // 获取失败，检查是否需要挂起
            if (shouldParkAfterFailedAcquire(p, node))
                interrupted |= parkAndCheckInterrupt();  // 挂起线程
        }
    } finally {
        if (failed)
            cancelAcquire(node);  // 取消获取
    }
}

// AQS.release() 流程
public final boolean release(int arg) {
    // 1. 尝试释放锁
    if (tryRelease(arg)) {
        Node h = head;
        if (h != null && h.waitStatus != 0)
            // 2. 唤醒后继节点
            unparkSuccessor(h);
        return true;
    }
    return false;
}

// unparkSuccessor: 唤醒后继节点
private void unparkSuccessor(Node node) {
    int ws = node.waitStatus;
    if (ws < 0)
        compareAndSetWaitStatus(node, ws, 0);  // 清除状态
    
    // 找到需要唤醒的节点
    Node s = node.next;
    if (s == null || s.waitStatus > 0) {
        s = null;
        // 从尾部向前查找最接近的未取消节点
        for (Node t = tail; t != null && t != node; t = t.prev)
            if (t.waitStatus <= 0)
                s = t;
    }
    
    // 唤醒线程
    if (s != null)
        LockSupport.unpark(s.thread);
}

public class ReentrantLock implements Lock {
    
    private final Sync sync;
    
    // 非公平锁实现
    static final class NonfairSync extends Sync {
        
        final void lock() {
            // 直接CAS尝试获取，不检查队列
            if (compareAndSetState(0, 1))
                setExclusiveOwnerThread(currentThread());
            else
                acquire(1);  // 进入AQS流程
        }
        
        protected final boolean tryAcquire(int acquires) {
            return nonfairTryAcquire(acquires);
        }
    }
    
    // Sync 基类
    abstract static class Sync extends AbstractQueuedSynchronizer {
        
        final boolean nonfairTryAcquire(int acquires) {
            final Thread current = Thread.currentThread();
            int c = getState();
            
            if (c == 0) {
                // 无锁状态，CAS获取
                if (compareAndSetState(0, acquires)) {
                    setExclusiveOwnerThread(current);
                    return true;
                }
            }
            else if (current == getExclusiveOwnerThread()) {
                // 重入：状态+1
                int nextc = c + acquires;
                if (nextc < 0)
                    throw new Error("Maximum lock count exceeded");
                setState(nextc);
                return true;
            }
            return false;
        }
        
        protected final boolean tryRelease(int releases) {
            int c = getState() - releases;
            if (Thread.currentThread() != getExclusiveOwnerThread())
                throw new IllegalMonitorStateException();
            
            boolean free = (c == 0);
            if (free)
                setExclusiveOwnerThread(null);
            setState(c);
            return free;
        }
    }
}

static final class FairSync extends Sync {
    
    final void lock() {
        acquire(1);  // 直接进入AQS流程，不插队
    }
    
    protected final boolean tryAcquire(int acquires) {
        final Thread current = Thread.currentThread();
        int c = getState();
        
        if (c == 0) {
            // 关键区别：检查队列中是否有等待线程
            if (!hasQueuedPredecessors() &&
                compareAndSetState(0, acquires)) {
                setExclusiveOwnerThread(current);
                return true;
            }
        }
        else if (current == getExclusiveOwnerThread()) {
            int nextc = c + acquires;
            if (nextc < 0)
                throw new Error("Maximum lock count exceeded");
            setState(nextc);
            return true;
        }
        return false;
    }
}

// hasQueuedPredecessors: 检查是否有前驱节点在等待
public final boolean hasQueuedPredecessors() {
    Node t = tail;
    Node h = head;
    Node s;
    
    // 队列不为空，且当前节点不是第一个等待的
    return h != t &&
        ((s = h.next) == null || s.thread != Thread.currentThread());
}

public class ReentrantReadWriteLock {
    
    // 状态位设计（32位int）
    // 高16位：读锁持有次数
    // 低16位：写锁重入次数
    
    static final int SHARED_SHIFT   = 16;
    static final int SHARED_UNIT    = (1 << SHARED_SHIFT);
    static final int MAX_COUNT      = (1 << SHARED_SHIFT) - 1;
    static final int EXCLUSIVE_MASK = (1 << SHARED_SHIFT) - 1;
    
    // 读锁计数（高16位）
    static int sharedCount(int c)    { return c >>> SHARED_SHIFT; }
    // 写锁计数（低16位）
    static int exclusiveCount(int c) { return c & EXCLUSIVE_MASK; }
    
    abstract static class Sync extends AbstractQueuedSynchronizer {
        
        // 读锁获取
        protected final int tryAcquireShared(int unused) {
            Thread current = Thread.currentThread();
            int c = getState();
            
            // 有写锁且不是当前线程持有，获取失败
            if (exclusiveCount(c) != 0 &&
                getExclusiveOwnerThread() != current)
                return -1;
            
            int r = sharedCount(c);
            // 读锁未满，CAS增加读锁计数
            if (r < MAX_COUNT && compareAndSetState(c, c + SHARED_UNIT)) {
                // 记录第一个读线程
                if (r == 0) {
                    firstReader = current;
                    firstReaderHoldCount = 1;
                } else if (firstReader == current) {
                    firstReaderHoldCount++;
                } else {
                    // 更新线程本地的读锁持有计数
                    HoldCounter rh = cachedHoldCounter;
                    if (rh == null || rh.tid != getThreadId(current))
                        cachedHoldCounter = rh = readHolds.get();
                    rh.count++;
                }
                return 1;
            }
            return fullTryAcquireShared(current);
        }
    }
}

public class LockDowngradeExample {
    
    private final ReentrantReadWriteLock rwLock = new ReentrantReadWriteLock();
    private final Lock readLock = rwLock.readLock();
    private final Lock writeLock = rwLock.writeLock();
    
    public void processData() {
        writeLock.lock();
        try {
            // 1. 修改数据
            modifyData();
            
            // 2. 降级为读锁（在释放写锁前获取读锁）
            readLock.lock();
            
        } finally {
            writeLock.unlock();  // 3. 释放写锁，仍持有读锁
        }
        
        try {
            // 4. 使用读锁读取数据
            readData();
        } finally {
            readLock.unlock();  // 5. 释放读锁
        }
    }
}

public class StampedLockExample {
    
    private final StampedLock sl = new StampedLock();
    private double x, y;
    
    // 乐观读
    public double distanceFromOrigin() {
        // 1. 获取乐观读戳记（不加锁）
        long stamp = sl.tryOptimisticRead();
        
        // 2. 读取共享变量
        double currentX = x;
        double currentY = y;
        
        // 3. 验证戳记（检查期间是否有写操作）
        if (!sl.validate(stamp)) {
            // 4. 验证失败，升级为悲观读锁
            stamp = sl.readLock();
            try {
                currentX = x;
                currentY = y;
            } finally {
                sl.unlockRead(stamp);
            }
        }
        
        return Math.sqrt(currentX * currentX + currentY * currentY);
    }
    
    // 写操作
    public void move(double deltaX, double deltaY) {
        long stamp = sl.writeLock();
        try {
            x += deltaX;
            y += deltaY;
        } finally {
            sl.unlockWrite(stamp);
        }
    }
}

public class ConditionObject implements Condition {
    
    // 条件队列头节点
    private transient Node firstWaiter;
    // 条件队列尾节点
    private transient Node lastWaiter;
    
    // await: 释放锁并等待
    public final void await() throws InterruptedException {
        // 1. 创建节点加入条件队列
        Node node = addConditionWaiter();
        
        // 2. 释放锁（保存状态）
        int savedState = fullyRelease(node);
        
        // 3. 在条件队列中等待
        while (!isOnSyncQueue(node)) {
            LockSupport.park(this);  // 挂起线程
            if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
                break;
        }
        
        // 4. 被唤醒后，重新获取锁
        acquireQueued(node, savedState, interruptMode);
    }
    
    // signal: 唤醒一个等待节点
    public final void signal() {
        if (!isHeldExclusively())
            throw new IllegalMonitorStateException();
        
        Node first = firstWaiter;
        if (first != null)
            doSignal(first);  // 将节点从条件队列转移到同步队列
    }
    
    private void doSignal(Node first) {
        do {
            if ((firstWaiter = first.nextWaiter) == null)
                lastWaiter = null;
            first.nextWaiter = null;
        } while (!transferForSignal(first) &&
                 (first = firstWaiter) != null);
    }
    
    final boolean transferForSignal(Node node) {
        // CAS更新状态
        if (!compareAndSetWaitStatus(node, Node.CONDITION, 0))
            return false;
        
        // 加入同步队列
        Node p = enq(node);
        int ws = p.waitStatus;
        if (ws > 0 || !compareAndSetWaitStatus(p, ws, Node.SIGNAL))
            LockSupport.unpark(node.thread);  // 唤醒线程
        return true;
    }
}

public class BoundedBuffer<T> {
    
    private final Lock lock = new ReentrantLock();
    private final Condition notFull = lock.newCondition();
    private final Condition notEmpty = lock.newCondition();
    
    private final Object[] items;
    private int putptr, takeptr, count;
    
    public BoundedBuffer(int capacity) {
        items = new Object[capacity];
    }
    
    public void put(T x) throws InterruptedException {
        lock.lock();
        try {
            // 缓冲区满，等待消费者
            while (count == items.length)
                notFull.await();
            
            items[putptr] = x;
            if (++putptr == items.length) putptr = 0;
            count++;
            
            // 唤醒消费者
            notEmpty.signal();
        } finally {
            lock.unlock();
        }
    }
    
    @SuppressWarnings("unchecked")
    public T take() throws InterruptedException {
        lock.lock();
        try {
            // 缓冲区空，等待生产者
            while (count == 0)
                notEmpty.await();
            
            T x = (T) items[takeptr];
            items[takeptr] = null;
            if (++takeptr == items.length) takeptr = 0;
            count--;
            
            // 唤醒生产者
            notFull.signal();
            return x;
        } finally {
            lock.unlock();
        }
    }
}

// 编程式死锁检测
public class DeadlockDetector {
    
    private final ThreadMXBean threadBean = ManagementFactory.getThreadMXBean();
    
    public void detectDeadlocks() {
        long[] threadIds = threadBean.findDeadlockedThreads();
        
        if (threadIds != null) {
            ThreadInfo[] threadInfos = threadBean.getThreadInfo(threadIds, true, true);
            
            for (ThreadInfo info : threadInfos) {
                System.out.println("Deadlock detected:");
                System.out.println("  Thread: " + info.getThreadName());
                System.out.println("  Blocked on: " + info.getLockName());
                System.out.println("  Lock owner: " + info.getLockOwnerName());
            }
        }
    }
}

// 策略1：固定加锁顺序
public class OrderedLockTransfer {
    
    private static final Object lock1 = new Object();
    private static final Object lock2 = new Object();
    
    public void transfer() {
        // 始终按相同顺序获取锁
        synchronized (lock1) {
            synchronized (lock2) {
                // 业务逻辑
            }
        }
    }
}

// 策略2：尝试获取锁（超时放弃）
public class TryLockExample {
    
    private final Lock lock1 = new ReentrantLock();
    private final Lock lock2 = new ReentrantLock();
    
    public void transfer() throws InterruptedException {
        while (true) {
            boolean gotLock1 = lock1.tryLock(100, TimeUnit.MILLISECONDS);
            boolean gotLock2 = lock2.tryLock(100, TimeUnit.MILLISECONDS);
            
            if (gotLock1 && gotLock2) {
                try {
                    // 业务逻辑
                    return;
                } finally {
                    lock1.unlock();
                    lock2.unlock();
                }
            }
            
            if (gotLock1) lock1.unlock();
            if (gotLock2) lock2.unlock();
            
            // 随机退避，避免活锁
            Thread.sleep(ThreadLocalRandom.current().nextInt(10, 100));
        }
    }
}

// 策略3：使用定时锁
public class TimedLockTransfer {
    
    private final Lock lock = new ReentrantLock();
    
    public boolean tryTransfer(long timeout, TimeUnit unit) throws InterruptedException {
        long deadline = System.nanoTime() + unit.toNanos(timeout);
        
        while (System.nanoTime() < deadline) {
            if (lock.tryLock(10, TimeUnit.MILLISECONDS)) {
                try {
                    // 业务逻辑
                    return true;
                } finally {
                    lock.unlock();
                }
            }
        }
        return false;  // 超时放弃
    }
}

// 差：锁住整个Map
public class CoarseGrainedCache {
    private final Map<String, Object> cache = new HashMap<>();
    
    public synchronized Object get(String key) {
        return cache.get(key);
    }
    
    public synchronized void put(String key, Object value) {
        cache.put(key, value);
    }
}

// 优：分段锁
public class FineGrainedCache {
    private static final int SEGMENTS = 16;
    private final Segment[] segments = new Segment[SEGMENTS];
    
    private static class Segment {
        final Map<String, Object> map = new HashMap<>();
        final ReentrantLock lock = new ReentrantLock();
    }
    
    public Object get(String key) {
        Segment segment = segments[key.hashCode() & (SEGMENTS - 1)];
        segment.lock.lock();
        try {
            return segment.map.get(key);
        } finally {
            segment.lock.unlock();
        }
    }
}

// 读写锁分离
public class ReadWriteLockCache {
    private final Map<String, Object> cache = new HashMap<>();
    private final ReentrantReadWriteLock rwLock = new ReentrantReadWriteLock();
    private final Lock readLock = rwLock.readLock();
    private final Lock writeLock = rwLock.writeLock();
    
    public Object get(String key) {
        readLock.lock();
        try {
            return cache.get(key);
        } finally {
            readLock.unlock();
        }
    }
    
    public void put(String key, Object value) {
        writeLock.lock();
        try {
            cache.put(key, value);
        } finally {
            writeLock.unlock();
        }
    }
}

// 使用CAS实现无锁栈
public class LockFreeStack<E> {
    
    private final AtomicReference<Node<E>> top = new AtomicReference<>();
    
    public void push(E item) {
        Node<E> newHead = new Node<>(item);
        Node<E> oldHead;
        do {
            oldHead = top.get();
            newHead.next = oldHead;
        } while (!top.compareAndSet(oldHead, newHead));
    }
    
    public E pop() {
        Node<E> oldHead;
        Node<E> newHead;
        do {
            oldHead = top.get();
            if (oldHead == null)
                return null;
            newHead = oldHead.next;
        } while (!top.compareAndSet(oldHead, newHead));
        return oldHead.item;
    }
    
    private static class Node<E> {
        final E item;
        Node<E> next;
        
        Node(E item) {
            this.item = item;
        }
    }
}

public class HighPerformanceCache<K, V> {
    
    // 使用 ConcurrentHashMap 做本地缓存
    private final ConcurrentHashMap<K, CacheEntry<V>> cache = new ConcurrentHashMap<>();
    
    // 读写锁保护热点数据
    private final ReentrantReadWriteLock rwLock = new ReentrantReadWriteLock();
    
    // 过期队列
    private final DelayQueue<DelayedEntry<K>> expireQueue = new DelayQueue<>();
    
    // 后台清理线程
    private final ScheduledExecutorService cleaner = Executors.newSingleThreadScheduledExecutor();
    
    public HighPerformanceCache() {
        // 定时清理过期数据
        cleaner.scheduleAtFixedRate(this::cleanExpired, 1, 1, TimeUnit.SECONDS);
    }
    
    public V get(K key) {
        // 1. 无锁读取
        CacheEntry<V> entry = cache.get(key);
        
        if (entry == null) {
            return null;
        }
        
        // 2. 检查是否过期
        if (entry.isExpired()) {
            // 3. 惰性删除
            cache.remove(key);
            return null;
        }
        
        // 4. 更新访问时间
        entry.touch();
        return entry.getValue();
    }
    
    public void put(K key, V value, long ttl, TimeUnit unit) {
        CacheEntry<V> entry = new CacheEntry<>(value, ttl, unit);
        
        // 使用 putIfAbsent 保证原子性
        CacheEntry<V> existing = cache.putIfAbsent(key, entry);
        
        if (existing != null) {
            // 更新现有条目
            existing.update(value, ttl, unit);
        } else {
            // 加入过期队列
            expireQueue.offer(new DelayedEntry<>(key, ttl, unit));
        }
    }
    
    public V computeIfAbsent(K key, Function<K, V> loader, long ttl, TimeUnit unit) {
        // 双重检查锁
        CacheEntry<V> entry = cache.get(key);
        if (entry != null && !entry.isExpired()) {
            return entry.getValue();
        }
        
        rwLock.writeLock().lock();
        try {
            entry = cache.get(key);
            if (entry != null && !entry.isExpired()) {
                return entry.getValue();
            }
            
            V value = loader.apply(key);
            put(key, value, ttl, unit);
            return value;
        } finally {
            rwLock.writeLock().unlock();
        }
    }
    
    private void cleanExpired() {
        List<DelayedEntry<K>> expired = new ArrayList<>();
        expireQueue.drainTo(expired);
        
        for (DelayedEntry<K> entry : expired) {
            cache.remove(entry.getKey());
        }
    }
    
    private static class CacheEntry<V> {
        private volatile V value;
        private volatile long expireTime;
        private volatile long lastAccessTime;
        
        CacheEntry(V value, long ttl, TimeUnit unit) {
            this.value = value;
            this.expireTime = System.nanoTime() + unit.toNanos(ttl);
            this.lastAccessTime = System.nanoTime();
        }
        
        boolean isExpired() {
            return System.nanoTime() > expireTime;
        }
        
        void touch() {
            this.lastAccessTime = System.nanoTime();
        }
        
        void update(V value, long ttl, TimeUnit unit) {
            this.value = value;
            this.expireTime = System.nanoTime() + unit.toNanos(ttl);
        }
        
        V getValue() {
            return value;
        }
    }
}