Прочитав его, вы поймете, что такое спин-блокировка серии замков.

Java

в предыдущей статьеПессимистический замок и оптимистичный замок, которые вы сможете понять после прочтенияМы узнали, что такое пессимистическая блокировка и оптимистичная блокировка, как реализовать пессимистическую блокировку и оптимистическую блокировку, а также каковы их преимущества и недостатки. В одной из реализаций оптимистичных блокировок, алгоритме CAS, упоминается концепция спиновой блокировки.Чтобы полностью понять алгоритм CAS, сначала нужно понять自旋锁Что это такое, каковы применимые сценарии и преимущества и недостатки спин-блокировок, не волнуйтесь, следующее перечислено для вас.

Фон блокировки спина

Из-за ограничения некоторых ресурсов в многопроцессорной среде иногда требуется взаимное исключение.В настоящее время необходимо ввести понятие блокировок.Только потоки, которые получают блокировки, могут получить доступ к ресурсам.Ядром является квант времени ЦП, поэтому одновременно получить блокировку может только один поток. Тогда возникает проблема, что должен делать поток, который не получает блокировку?

Обычно существует два метода обработки: один заключается в том, что поток, который не получил блокировку, продолжает ждать в цикле, чтобы определить, освободил ли ресурс блокировку. поток (НЕБЛОКИРУЕМЫЙ); другой Один из способов справиться с этим — заблокировать себя и дождаться перепланированного запроса, который называется互斥锁.

Что такое спин-блокировка

Определение спин-блокировки: когда поток пытается получить блокировку, если блокировка была получена (занята) кем-то другим в это время, тогда поток не может получить блокировку, и поток будет ждать в течение интервала. Попробует снова через какое-то время. Этот механизм использования циклической блокировки -> ожидание называется自旋锁(spinlock).

file

Принцип блокировки вращения

Принцип спин-блокировки относительно прост: если поток, удерживающий блокировку, может освободить ресурс блокировки за короткое время, то потокам, ожидающим конкурирующую блокировку, не нужно переключаться между режимом ядра и пользовательским режимом, чтобы войти в режим блокировки. в состоянии блокировки, им нужно только подождать минуту (прокрутить), дождаться, пока поток, удерживающий блокировку, освободит блокировку, а затем получить ее, избегая, таким образом, потребления пользовательских процессов и переключения ядра.

Поскольку спин-блокировки позволяют избежать планирования процессов операционной системы и переключения потоков, спин-блокировки обычно подходят для коротких периодов времени. по этой причине,Ядро операционной системы часто использует спин-блокировки.. Однако при длительной блокировке спин-блокировка может быть очень дорогостоящей, поскольку она препятствует запуску и планированию других потоков. Чем дольше нить удерживает замок, тем нить, удерживающая замок, будетOS(Operating System)Чем выше риск сбоев планировщика. В случае прерывания другие потоки будут продолжать вращаться (неоднократно пытаясь получить блокировку), а поток, удерживающий блокировку, не собирается снимать блокировку, что приводит к неопределенной задержке, пока поток, удерживающий блокировку, не сможет завершить и освободить блокировку. Это.

Хороший способ решить описанную выше ситуацию — установить время вращения для блокировки вращения и снять блокировку вращения, как только время истечет. Назначение спин-блокировок состоит в том, чтобы занимать ресурсы ЦП, не освобождая их, и обрабатывать их сразу после получения блокировок. Но как выбрать время отжима? Если время выполнения вращения слишком велико, большое количество потоков будет находиться в состоянии вращения и занимать ресурсы ЦП, что повлияет на производительность всей системы. Поэтому выбор периода вращения имеет особое значение! В JDK 1.6 введены адаптивные спин-блокировки. Адаптивные спин-блокировки означают, что время вращения не фиксировано, а определяется предыдущим временем вращения на той же блокировке и состоянием блокировки. В основном считается, что время для контекста потока Переключение — оптимальное время.

Преимущества и недостатки спин-блокировок

Спин-блокировки максимально сокращают блокировку потоков, что может значительно повысить производительность для блоков кода, которые не имеют интенсивной конкуренции за блокировки и занимают очень короткое время блокировки, потому что потребление спина будет меньше, чем при блокировке и приостановке потока, а затем пробуждения, операции, вызывающие два переключения контекста для потока!

Однако, если конкуренция между блокировками высока или поток, удерживающий блокировку, должен занимать блокировку в течение длительного времени, чтобы выполнить блок синхронизации, использование спин-блокировки в это время нецелесообразно, потому что спин-блокировка всегда занимает блокировку. ЦП для бесполезной работы перед получением блокировки.Когда XX не XX, и существует большое количество потоков, конкурирующих за блокировку одновременно, получение блокировки займет много времени, потребление вращения потока больше чем потребление операций блокировки и приостановки потока, а другие потоки, которым нужен ЦП, не могут получить ЦП, что приводит к растрате ЦП. Так что в этом случае мы должны отключить спин-блокировку.

Реализация спиновой замок

Ниже мы используем код Java для реализации простой спин-блокировки.

public class SpinLockTest {

    private AtomicBoolean available = new AtomicBoolean(false);

    public void lock(){

        // 循环检测尝试获取锁
        while (!tryLock()){
            // doSomething...
        }

    }

    public boolean tryLock(){
        // 尝试获取锁，成功返回true，失败返回false
        return available.compareAndSet(false,true);
    }

    public void unLock(){
        if(!available.compareAndSet(true,false)){
            throw new RuntimeException("释放锁失败");
        }
    }

}

У этой простой спин-блокировки есть одна проблема:Невозможно гарантировать честность многопоточной конкуренции. Для SpinlockTest выше, когда несколько потоков хотят получить блокировку, кто будет первымavailableустановить какfalseКто может получить блокировку первым, что может привести к тому, что некоторые потоки никогда не получат блокировку.线程饥饿. Точно так же, как мы ломились в столовую после уроков и толпились в метро после работы, мы обычно решаем такие проблемы с помощью очереди.QueuedSpinlock. Ученые-компьютерщики использовали различные способы реализации спин-блокировок с очередями, такие как TicketLock, MCSLock, CLHLock. Далее мы дадим общее представление об этих типах замков.

TicketLock

В компьютерных науках TicketLock — это механизм синхронизации или алгоритм блокировки, представляющий собой спин-блокировку, использующуюticketдля управления порядком выполнения потоков.

Как система управления очередью билетов. Пекарни или предприятия сферы обслуживания (такие как банки) используют этот метод для записи порядка прибытия каждого клиента, который приходит первым, без очереди каждый раз. Обычно в такого рода месте будет раздатчик (звонилка, регистрационное устройство и т.д.), и тому, кто придет первым, нужно вынуть номер, который он сейчас стоит в очереди на этом автомате.Этот номер находится в порядке само- увеличивается, Рядом с ним также будет знак, показывающий обслуживаемый знак, который обычно представляет номер очереди, обслуживаемой в настоящее время.После того, как текущий номер завершит обслуживание, знак покажет, что следующий номер готов к обслуживанию.

Как и описанная выше система, TicketLock основан на механизме очереди «первым пришел – первым обслужен» (FIFO). Он повышает честность блокировки, а принципы его построения таковы: В TicketLock есть два значения типа int, начало равно 0, а первое значение равно队列ticket(队列票据), второе значение出队(票据). Билет очереди — это позиция потока в очереди, а билет удаления из очереди — это позиция в очереди билета, который теперь удерживает блокировку. Это может быть немного расплывчато, если говорить простыми словами,То есть билет очереди — это место, где вы получаете номер билета, а билет очереди — это место, где вы звоните по этому номеру.. Теперь должно быть яснее.

Когда вам звонят по номеру, у вас не может быть одного и того же номера для одновременного управления бизнесом.Должен быть только один человек, который может это сделать.После завершения звонка машина для набора номера позвонит следующему человеку.Это называется原子性. Вас не могут отвлекать другие люди, когда вы занимаетесь бизнесом, и два человека с одним и тем же номером не могут вести бизнес одновременно. Затем следующий человек видит, совпадает ли его номер с вызываемым номером.Если они совпадают, то наступает ваша очередь делать дело, иначе вы можете только продолжать ждать.Ключевым моментом вышеописанного процесса является то, что после того, как каждый деловой человек завершит дело, он должен сбросить свой собственный номер, а машина для вызова номера может продолжать звонить следующему человеку.Если человек не сбрасывает номер, то только другие люди. можно продолжать ждать. Давайте реализуем эту схему очереди билетов

public class TicketLock {

    // 队列票据(当前排队号码)
    private AtomicInteger queueNum = new AtomicInteger();

    // 出队票据(当前需等待号码)
    private AtomicInteger dueueNum = new AtomicInteger();

    // 获取锁：如果获取成功，返回当前线程的排队号
    public int lock(){
        int currentTicketNum = dueueNum.incrementAndGet();
        while (currentTicketNum != queueNum.get()){
            // doSomething...
        }
        return currentTicketNum;
    }

    // 释放锁：传入当前排队的号码
    public void unLock(int ticketNum){
        queueNum.compareAndSet(ticketNum,ticketNum + 1);
    }

}

Каждый раз, когда машина, вызывающая номер, вызывает номер, она определяет, является ли этот номер вызываемым, и когда все завершают работу, машина, вызывающая номер, добавляет 1 на основе текущего номера, чтобы очередь продолжала двигаться вперед.

Однако приведенная выше конструкция проблематична, так как после получения собственного номера вы можете изменить номер, что приводит к нарушению работы системы и невозможности вовремя снять блокировку. В настоящее время должна быть роль, которая может гарантировать, что каждый будет стоять в очереди, чтобы заниматься бизнесом в соответствии со своими собственными номерами.Узнав это, мы перерабатываем логику

public class TicketLock2 {

    // 队列票据(当前排队号码)
    private AtomicInteger queueNum = new AtomicInteger();

    // 出队票据(当前需等待号码)
    private AtomicInteger dueueNum = new AtomicInteger();

    private ThreadLocal<Integer> ticketLocal = new ThreadLocal<>();

    public void lock(){
        int currentTicketNum = dueueNum.incrementAndGet();

        // 获取锁的时候，将当前线程的排队号保存起来
        ticketLocal.set(currentTicketNum);
        while (currentTicketNum != queueNum.get()){
            // doSomething...
        }
    }

    // 释放锁：从排队缓冲池中取
    public void unLock(){
        Integer currentTicket = ticketLocal.get();
        queueNum.compareAndSet(currentTicket,currentTicket + 1);
    }

}

На этот раз возвращаемое значение больше не нужно.При ведении бизнеса нужно кешировать текущий номер.После завершения дела нужно освободить кешированный тикет.

недостаток

Хотя TicketLock решает проблему справедливости, в многопроцессорной системе процессоры, занятые каждым процессом/потоком, считывают и записывают одну и ту же переменную queueNum, и каждая операция чтения и записи должна выполняться между кэшами нескольких процессоров Синхронизация кэша, что приводит в интенсивном трафике системной шины и памяти значительно снижает общую производительность системы.

Чтобы решить эту проблему, MCSLOCK и CLHLOCK пришли.

CLHLock

Говоря выше, TicketLock основан на очереди, тогда список CLHLock основан на дизайне изобретателя CLH: Craig, Landin и Hagersten, начинаются с их соответствующего буквенного обозначения. CLH основан на списке масштабируемых, высокопроизводительных, справедливых спин-блокировок, поток может применять только спин для локальной переменной, он будет продолжать опрашивать состояние предшественника, если мы найдем предшественника, чтобы снять блокировку. конец вращения.

public class CLHLock {

    public static class CLHNode{
        private volatile boolean isLocked = true;
    }

    // 尾部节点
    private volatile CLHNode tail;
    private static final ThreadLocal<CLHNode> LOCAL = new ThreadLocal<>();
    private static final AtomicReferenceFieldUpdater<CLHLock,CLHNode> UPDATER =
            AtomicReferenceFieldUpdater.newUpdater(CLHLock.class,CLHNode.class,"tail");


    public void lock(){
        // 新建节点并将节点与当前线程保存起来
        CLHNode node = new CLHNode();
        LOCAL.set(node);

        // 将新建的节点设置为尾部节点，并返回旧的节点（原子操作），这里旧的节点实际上就是当前节点的前驱节点
        CLHNode preNode = UPDATER.getAndSet(this,node);
        if(preNode != null){
            // 前驱节点不为null表示当锁被其他线程占用，通过不断轮询判断前驱节点的锁标志位等待前驱节点释放锁
            while (preNode.isLocked){

            }
            preNode = null;
            LOCAL.set(node);
        }
        // 如果不存在前驱节点，表示该锁没有被其他线程占用，则当前线程获得锁
    }

    public void unlock() {
        // 获取当前线程对应的节点
        CLHNode node = LOCAL.get();
        // 如果tail节点等于node，则将tail节点更新为null，同时将node的lock状态职位false，表示当前线程释放了锁
        if (!UPDATER.compareAndSet(this, node, null)) {
            node.isLocked = false;
        }
        node = null;
    }
}

MCSLock

MCS Spinlock – это масштабируемая, высокопроизводительная и справедливая циклическая блокировка, основанная на связанных списках. Поток приложения использует только локальные переменные, а непосредственный предшественник отвечает за уведомление об окончании цикла, что значительно сокращает ненужные кэши процессора. синхронизаций снижает нагрузку на шину и память. MCS происходит от инициалов его изобретателей: Джона Меллора-Крамми и Майкла Скотта.

public class MCSLock {

    public static class MCSNode {
        volatile MCSNode next;
        volatile boolean isLocked = true;
    }

    private static final ThreadLocal<MCSNode> NODE = new ThreadLocal<>();

    // 队列
    @SuppressWarnings("unused")
    private volatile MCSNode queue;

    private static final AtomicReferenceFieldUpdater<MCSLock,MCSNode> UPDATE =
            AtomicReferenceFieldUpdater.newUpdater(MCSLock.class,MCSNode.class,"queue");


    public void lock(){
        // 创建节点并保存到ThreadLocal中
        MCSNode currentNode = new MCSNode();
        NODE.set(currentNode);

        // 将queue设置为当前节点，并且返回之前的节点
        MCSNode preNode = UPDATE.getAndSet(this, currentNode);
        if (preNode != null) {
            // 如果之前节点不为null，表示锁已经被其他线程持有
            preNode.next = currentNode;
            // 循环判断，直到当前节点的锁标志位为false
            while (currentNode.isLocked) {
            }
        }
    }

    public void unlock() {
        MCSNode currentNode = NODE.get();
        // next为null表示没有正在等待获取锁的线程
        if (currentNode.next == null) {
            // 更新状态并设置queue为null
            if (UPDATE.compareAndSet(this, currentNode, null)) {
                // 如果成功了，表示queue==currentNode,即当前节点后面没有节点了
                return;
            } else {
                // 如果不成功，表示queue!=currentNode,即当前节点后面多了一个节点，表示有线程在等待
                // 如果当前节点的后续节点为null，则需要等待其不为null（参考加锁方法）
                while (currentNode.next == null) {
                }
            }
        } else {
            // 如果不为null，表示有线程在等待获取锁，此时将等待线程对应的节点锁状态更新为false，同时将当前线程的后继节点设为null
            currentNode.next.isLocked = false;
            currentNode.next = null;
        }
    }
}

CLHLock и MCSLock

  • Все они основаны на связанных списках. Разница в том, что CLHLock основан на неявном связанном списке и не имеет реальных атрибутов последующих узлов. MCSLock — это отображаемый связанный список с атрибутом, указывающим на последующие узлы.
  • Состояние потока, получившего блокировку, сохраняется узлом (узлом), и каждый поток имеет независимый узел, что решает проблему синхронизации многопроцессорного кеша TicketLock.

Суммировать

В этой статье мы в основном описываем предысторию спин-блокировок. Спин-блокировки — это разновидность блокировок, которые, по-видимому, увеличивают частоту использования ресурсов. Спин-блокировки означают, что когда поток получает блокировку, если блокировка удерживается другими потоками, текущий поток будет ждать в цикле, пока не будет получена блокировка.

Спиновые замки не освободят свою собственную нить или сон во время ожидания. Спинлокны не применяются к держателям времени ЦП, что усугубит бремя на систему, чтобы решить эту ситуацию, необходимо установить цикл спина, затем установить цикл спина также наука.

Также упоминается, что спин-блокировка сама по себе не может гарантировать справедливость, поэтому для обеспечения справедливости вводится TicketLock, разновидность честной блокировки, реализованная с использованием механизма очередей и вызовов, но каждая операция чтения и записи должна выполняться. в нескольких кэшах синхронизация между кэшами процессоров приводит к увеличению нагрузки на системную шину и память и значительно снижает общую производительность системы.

Поэтому мы представляем CLHLock и MCSLock. CLHLock и MCSLock позволяют избежать сокращения синхронизации кэша процессора с помощью связанного списка, что значительно повышает производительность. Разница в том, что CLHLock опрашивает состояние предшествующих узлов, а MCS проверяет состояние предшествующих узлов. Состояние блокировки текущего узла.

Ссылка на статью:

https://blog.csdn.net/qq_34337272/article/details/81252853

http://www.blogjava.net/jinfeng_wang/archive/2016/12/14/432088.html

https://blog.hufeifei.cn/ Статьи о спин-блокировках

https://en.wikipedia.org/wiki/Ticket_lock

Сделайте рекламу для себя ниже, пожалуйста, обратите внимание на общедоступный номерJava建设者, Владелец представляет собой стек технологий Java, любит технологии, любит читать, любит делиться и подводить итоги и надеется поделиться с вами каждой хорошей статьей на пути роста. Обратите внимание на ответ на общедоступный номер002Получите гулянку, специально приготовленную для вас, вы полюбите ее и соберете.

file

Эта статья опубликована в блогеOpenWriteвыпускать!

Категории