Введение в параллельное программированиедля распределенных вычислений -Параллельное программирование https://url.wx-coder.cn/Yagu8Краткое содержание и краткое содержание сериала.

Введение в параллельное программирование

С быстрым развитием производительности оборудования и наступлением эры больших данных параллельное программирование все чаще становится важной частью программирования, которую нельзя игнорировать. По определению исполнительные блоки являются параллельными, если их логический поток управления перекрывается во времени. Основной движущей силой ренессанса параллельного программирования является так называемый «многоядерный кризис». Производительность чипа по-прежнему улучшается, как и предсказывает закон Мура, но компьютеры движутся в сторону многоядерности по сравнению с ускорением процессоров. По словам Херба Саттера, «эпоха бесплатных обедов закончилась». Чтобы код работал быстрее, полагаясь исключительно на более быстрое оборудование, больше не может соответствовать требованиям, параллельные и распределенные вычисления являются основным содержанием современных приложений, нам необходимо использовать несколько ядер или несколько машин для ускорения приложений или запуска крупномасштабных Oни.

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

В этом разделе в основном обсуждается содержание, связанное с теорией параллельного программирования, вы можете обратиться к [Параллельное программирование на Java https://url.wx-coder.cn/72vCj,Перейти на параллельное программирование https://url.wx-coder.cn/FO9EXЧтобы понять практику параллельного программирования на конкретных языках программирования, вы можете обратиться кБоевой микросервис https://url.wx-coder.cn/7KZ2iилиТеория реляционных баз данных https://url.wx-coder.cn/DJNQnУзнайте о параллельном программировании в реальных системах.

Параллелизм и параллелизм

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

Короче говоря, параллелизм — это способность работать с несколькими задачами одновременно, а параллелизм — это способность выполнять несколько задач одновременно.

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

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

A single-threaded program can definitely provides concurrency at the IO level by using an IO (de)multiplexing mechanism and an event loop (which is what Redis does).

параллелизм на уровне потоков

С появлением разделения времени в начале 1960-х компьютерные системы поддерживали параллельное выполнение; традиционно такое параллельное выполнение моделировалось только с помощью компьютера. Быстрое переключение достигается в конфигурации, называемой однопроцессорной системой. Начиная с 1980-х годов, многопроцессорные системы, т. е. системы, состоящие из нескольких процессоров, управляемых одним ядром операционной системы, использовали такие технологии, как многоядерные процессоры и HyperThreading, которые позволили нам достичь истинного параллелизма. Многоядерный процессор объединяет несколько процессоров на одном кристалле интегральной схемы:

Гиперпоточность, иногда называемая одновременной многопоточностью, представляет собой технологию, которая позволяет одному процессору выполнять несколько потоков управления. Он включает в себя несколько копий некоторых аппаратных частей ЦП, таких как программный счетчик и регистровый файл, в то время как другие аппаратные части имеют только одну копию, например блок, выполняющий арифметические операции с плавающей запятой. В то время как обычным процессорам требуется около 20 000 тактовых циклов для переключения между потоками, процессоры с гиперпоточностью могут решить, какой поток выполнять за один цикл. Это позволяет процессору лучше использовать свои вычислительные ресурсы. Например, предположим, что один поток должен дождаться загрузки некоторых данных в кэш, после чего ЦП может продолжить выполнение другого потока.

параллелизм на уровне инструкций

На более низком уровне абстракции свойство современных процессоров выполнять несколько инструкций одновременно называется параллелизмом на уровне инструкций. На самом деле каждая инструкция от начала до конца занимает гораздо больше времени, порядка 20 и более циклов, но процессор использует множество хитрых уловок, чтобы обрабатывать до 100 инструкций одновременно. При конвейерной обработке действия, необходимые для выполнения инструкции, делятся на разные этапы, а аппаратное обеспечение процессора организовано в ряд этапов, каждый из которых выполняет определенный шаг. Эти этапы могут работать параллельно для обработки разных частей разных инструкций. Мы увидим довольно простую аппаратную конструкцию, которая может обеспечить скорость выполнения, близкую к одной инструкции за такт. Если процессор может достичь более высокой скорости выполнения, чем одна инструкция за такт, он называется суперскалярным (Super Scalar) процессором.

Одна инструкция, несколько данных

На самом низком уровне многие современные процессоры имеют специальное оборудование, которое позволяет одной инструкции выполнять несколько операций, которые могут выполняться параллельно, что называется параллелизмом с одной инструкцией, несколькими данными или SIMD. Например, более новые процессоры Intel и AMD имеют инструкции для параллельного добавления 4 пар чисел с плавающей запятой одинарной точности (тип данных C float).

модель памяти

Как упоминалось ранее, современные компьютеры обычно имеют два или более ЦП, а некоторые ЦП имеют несколько ядер; это позволяет одновременно выполнять несколько потоков, при этом каждый ЦП запускает один из этих потоков в течение определенного интервала времени. существуетУправление хранилищем https://parg.co/Z47В этом разделе мы представили различные классы памяти в компьютерных системах:

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

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

видимость

Так называемая видимость, то есть модификация разделяемой переменной потоком, которую сразу может увидеть другой поток. В эпоху одноядерных процессоров все потоки напрямую манипулируют данными одного ЦП, и запись в кэш потоком должна быть видна другому потоку; например, на следующем рисунке, если поток B обновляет значение переменной в thread A Доступ сделан, то необходимо получить самое последнее значение переменной V. В эпоху многоядерности каждый ЦП имеет собственный кеш, а общие переменные хранятся в основной памяти. Поток, работающий на ЦП, считывает общую переменную в свой собственный кэш ЦП. В кэше ЦП изменяется значение общего объекта, и, поскольку ЦП не сбрасывает данные из кэша обратно в основную память, изменение общей переменной невидимо для потока, работающего в другом ЦП. Таким образом, у каждого потока будет копия собственной общей переменной, которая хранится в соответствующем кэше процессора.

Самый классический случай проблемы видимости — параллельная операция сложения.Следующие два потока одновременно обновляют значение поля атрибута count переменной test.В первый раз count=0 будет прочитан в соответствующий ЦП caches, и выполнение будет завершено.count+=1После этого значения в соответствующих кешах ЦП все равны 1, и после одновременной записи в память мы обнаружим, что память равна 1, а не 2, которые мы ожидали. После этого, поскольку соответствующие кэши ЦП имеют значение count, оба потока вычисляются на основе значения count в кэше ЦП, поэтому окончательное значение count меньше 20000.

Thread th1 = new Thread(()->{
    test.add10K();
});

Thread th2 = new Thread(()->{
    test.add10K();
});

// 每个线程中对相同对象执行加操作
count += 1;

В Java, если несколько потоков совместно используют объект, а объявление volatile и синхронизация потоков не используются разумно, после того, как один поток обновит общий объект, другой поток не сможет получить последнее значение объекта. Когда общая переменная является энергозависимой, это гарантирует, что измененное значение будет немедленно обновлено в основной памяти, и когда другому потоку потребуется его прочитать, оно отправится в память для чтения нового значения. Видимость также может быть гарантирована с помощью synchronized и Lock, Synchronized и Lock могут гарантировать, что только один поток получает блокировку одновременно, а затем выполняет синхронизированный код, а изменения переменных сбрасываются в основную память перед снятием блокировки. Так что видимость гарантирована.

атомарность

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

i++

# 编译成汇编之后就是：
# 读取当前变量 i 并把它赋值给一个临时寄存器;
movl i(%rip), %eax
# 给临时寄存器+1;
addl $1, %eax
# 把 eax 的新值写回内存
movl %eax, i(%rip)

Мы ясно видим, что коду C требуется только одно предложение, но для его компиляции в сборку требуется три шага (оптимизация компилятора здесь не рассматривается, на самом деле три инструкции сборки можно объединить в одну с помощью оптимизации компилятора). Другими словами, только простое чтение и присваивание (и должны присваивать номер переменной, взаимное присваивание между переменными не является атомарной операцией) являются атомарными операциями. Проблема синхронизации решается методом атомарной операции: опираясь на поддержку примитивов процессора, три вышеуказанные инструкции объединяются в одну и выполняются как одна инструкция, чтобы гарантировать, что процесс выполнения не будет прерван, а многопоточный параллелизм не будет не беспокоить. Таким образом легко решается проблема синхронизации, которая представляет собой так называемую атомарную операцию. Однако процессор не обязан обеспечивать атомарные операции для любого фрагмента кода, тем более, что ресурсы нашей критической секции очень велики или даже неопределенного размера, процессору не нужно и не сложно обеспечивать атомарную поддержку. часто необходимо полагаться на блокировки для обеспечения атомарности.

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

упорядоченность

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

Например:

int a = 1, b = 2, c = 3;
void test() {
    a = b + 1;
    b = c + 1;
    c = a + b;
}

Код тела тестовой функции ассемблерного кода в gcc выглядит следующим образом, где параметры компиляции: -O0

movl b(%rip), %eax
addl $1, %eax
movl %eax, a(%rip)
movl c(%rip), %eax
addl $1, %eax
movl %eax, b(%rip)
movl a(%rip), %edx
movl b(%rip), %eax
addl %edx, %eax
movl %eax, c(%rip)

Параметр компиляции: -O3

movl b(%rip), %eax                  ;将b读入eax寄存器
leal 1(%rax), %edx                  ;将b+1写入edx寄存器
movl c(%rip), %eax                  ;将c读入eax
movl %edx, a(%rip)                  ;将edx写入a
addl $1, %eax                       ;将eax+1
movl %eax, b(%rip)                  ;将eax写入b
addl %edx, %eax                     ;将eax+edx
movl %eax, c(%rip)                  ;将eax写入c

Классическая проблема, связанная с упорядочением в Java, — это режим singleton.Например, мы будем использовать статическую функцию для получения экземпляра объекта и использовать синхронизированную блокировку, чтобы гарантировать, что только один поток может инициировать создание, а другие потоки могут получить его непосредственно в объект экземпляра.

if (instance == null) {
    synchronized(Singleton.class) {
    if (instance == null)
        instance = new Singleton();
    }
}

Однако, хотя процесс создания объекта, который мы ожидаем, состоит из выделения памяти, инициализации объектов и присвоения ссылок на объекты переменным-членам, на практике оптимизированный код часто сначала присваивает переменные, а затем инициализирует объекты. Предполагая, что поток A сначала выполняет метод getInstance(), когда выполняется инструкция 2, происходит переключение потока и он переключается на поток B; если поток B в это время также выполняет метод getInstance(), то поток B выполняет первое суждение .найдетinstance != null, поэтому экземпляр возвращается напрямую, и экземпляр в это время не был инициализирован.Если мы получим доступ к переменным-членам экземпляра в это время, может быть вызвано исключение нулевого указателя.

барьер памяти

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

POSIX, C++ и Java имеют свои собственные модели разделяемой памяти, и нет никакой разницы в реализации, только немного отличаются некоторые детали. Упомянутая здесь модель памяти относится не к структуре памяти, а конкретно к памяти, кэшу, ЦП, буферам записи, регистрам и другим аппаратным средствам и оптимизации компилятора, которые обеспечивают защиту операций чтения и записи инструкций для обеспечения порядка чтения и записи. Эти сложные факторы можно в общих чертах разделить на два аспекта: перестановка и кеш, а именно перестановка кода, перестановка инструкций и кэш-память ЦП, упомянутые выше. Проще говоря, барьеры памяти делают две вещи:Отказаться от переупорядочивания, обновить кеш.

C++11 предоставляет набор пользовательских API std::memory_order для управления порядком чтения и записи процессора. Java использует правила «происходит до» для маскировки определенных гарантий, предписывая JVM чередовать барьерные инструкции во время генерации инструкций. Барьер памяти также может указывать во время компиляции, что инструкции или последовательности, включая окружающие инструкции, не оптимизированы.Он называется барьером компилятора и эквивалентен облегченному барьеру памяти.Его работа не менее важна, поскольку он направляет оптимизацию компилятора во время компиляции. Реализация барьеров немного сложнее, и мы используем абстрактный набор гипотетических инструкций, чтобы описать, как работают барьеры памяти. Используйте MB_R, MB_W, MB, чтобы абстрагировать инструкции процессора в макросы:

MB_R означает барьер чтения памяти, который гарантирует, что операции чтения не будут переупорядочены после вызова этой инструкции.
MB_W означает барьер записи в память, который гарантирует, что операции записи не будут переупорядочены после вызова этой инструкции.
МБ представляет собой барьер памяти для чтения и записи, гарантирующий, что предыдущая инструкция не изменит порядок вызова инструкции.

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

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

Модель памяти Java (JMM)

Модель памяти Java фокусируется на описании того, как потоки в Java взаимодействуют с памятью, а также на порядке выполнения кода в одном потоке, и обеспечивает ряд основных семантических принципов параллелизма; самая ранняя модель памяти Java была предложена в 1995 году и посвящена решению проблемы. проблема взаимодействия/синхронизации потоков в разных процессорах/операционных системах, а также спецификация и управление программами Java для детерминированного поведения в разных архитектурах памяти, процессорах и операционных системах. До Java 5 JMM не была идеальной, и многопоточность часто считывала много странных данных в разделяемую память; например, поток не мог видеть значение, записанное в разделяемую переменную другими потоками, или из-за проблем с переупорядочением инструкций, где один поток может видеть странные шаги в других потоках.

Модель памяти Java имеет некоторую врожденную «упорядоченность», то есть упорядоченность, которая может быть гарантирована без каких-либо средств, что часто называют принципом «происходит до». Если порядок выполнения двух операций не может быть выведен из принципа «происходит до», то они не могут гарантировать их порядок, и виртуальная машина может изменить их порядок по своему желанию.

Модель памяти Java гарантирует, что изменения, сделанные одним потоком, могут быть видны другим потокам, и между ними существует отношение «произошло до».

Код внутри потока может выполняться последовательно, что называетсяправила порядка программы.
Для одной и той же блокировки операция разблокировки должна выполняться до другой операции блокировки, которая выполняется по прошествии некоторого времени, также называемойПравила блокировки монитора.
Предыдущая запись в volatile предшествует последующему чтению volatile, также называемомуправила изменяемой переменной.
Любая операция в потоке должна следовать за вызовом потока start(), также известным какправило начала потока.
Все операции потока выполняются до завершения потока.правила завершения потока.
Операция завершения объекта должна быть завершена после создания объекта, также называемаяПравила завершения объекта.

Для правил порядка выполнения программы выполнение части программного кода представляется упорядоченным в одном потоке. Обратите внимание, что хотя в этом правиле упоминается, что «операция, написанная впереди, выполняется до операции, написанной сзади», это должен быть порядок, в котором программа выполняется в порядке кода, потому что виртуальная машина может выполнять операции над программой. код Переупорядочивание инструкций. Несмотря на то, что выполняется переупорядочение, окончательный результат выполнения согласуется с результатом последовательного выполнения программы, и он будет переупорядочивать только те инструкции, которые не имеют зависимостей от данных. Таким образом, в рамках одного потока выполнение программы выполняется по порядку, что следует тщательно понимать. Фактически это правило используется для обеспечения корректности результатов выполнения программы в одном потоке, но оно не может гарантировать корректность выполнения программы в нескольких потоках.

Процессы, потоки и сопрограммы

В системе без конфигурации ОС режим выполнения программ — последовательное выполнение, то есть одна программа должна быть выполнена до того, как будет разрешено выполнение другой программы; в мультипрограммной среде допускается одновременное выполнение нескольких программ. Между этими двумя способами выполнения программы есть существенные различия. Именно эта особенность одновременного выполнения программ привела к введению концепции процессов в операционную систему.Процесс — это основная единица распределения ресурсов, а поток — основная единица планирования ресурсов..

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

Процесс | Процесс

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

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

существуетУправление виртуальным хранилищем https://url.wx-coder.cn/PeNqSВ этом разделе мы представили, что это дает каждому процессу иллюзию того, что каждый процесс использует исключительно основную память. Каждый процесс видит непротиворечивую память, называемую виртуальным адресным пространством. Верхняя область его виртуального адресного пространства зарезервирована для кода и данных в операционной системе, которая одинакова для всех процессов; нижняя область адресного пространства содержит код и данные, определенные пользовательскими процессами.

Программный код и данные для всех процессов, код должен начинаться с одного и того же фиксированного адреса, непосредственно исполняемый объект инициализируется в соответствии с содержимым файла.
За кучей, кодом и областями данных следует куча времени выполнения. В отличие от областей кода и данных, размер которых определяется при запуске процесса, куча может динамически расширяться и сжиматься во время выполнения при вызове функций стандартной библиотеки C, таких как malloc и free.
Совместно используемые библиотеки. Примерно в середине адресного пространства находится область кода и данных для общих библиотек, таких как стандартная библиотека C и математическая библиотека.
Стек в верхней части пользовательского виртуального адресного пространства — это пользовательский стек, который компилятор использует для реализации вызовов функций. Как и куча, пользовательский стек может динамически расширяться и сжиматься во время выполнения программы.
Виртуальная память ядра: ядро всегда находится в памяти и является частью операционной системы. Область в верхней части адресного пространства зарезервирована для ядра, и приложениям не разрешено читать или записывать содержимое этой области или напрямую вызывать функции, определенные кодом ядра.

нить | нить

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

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

Идентификатор потока: каждый поток имеет свой собственный идентификатор потока, который уникален в пределах процесса. Процессы используют это для идентификации потоков.
Значение набора регистров: Поскольку потоки выполняются одновременно, каждый поток имеет свои собственные различные рабочие подсказки. При переключении с одного потока на другой поток должен сохранять состояние набора регистров исходного потока для будущего использования. Поток может быть возобновлено, когда он переключится обратно.
Стек потока: стек необходим для обеспечения независимого выполнения потоков. Функции потоков могут вызывать функции, а вызываемые функции могут быть вложены в слои, поэтому поток должен иметь собственный стек функций, чтобы вызов функции мог выполняться нормально, не подвергаясь влиянию других потоков.
Код возврата ошибки: поскольку в одном и том же процессе одновременно выполняется много потоков, возможно, что поток устанавливает значение errno после выполнения системного вызова, а поток еще не обработал ошибку, и запланирован другой поток. планировщиком в это время введен в действие, так что значение ошибки может быть изменено. Таким образом, разные потоки должны иметь свои собственные переменные кода возврата ошибки.
Код маски сигнала потока: поскольку каждый поток заинтересован в разных сигналах, код маски сигнала потока должен управляться самой резьбой. Но все темы имеют один и тот же обработчик сигналов.
Приоритет потока: поскольку поток необходимо планировать так же, как и процесс, для планирования должен быть доступен параметр — приоритет потока.

Потоки в Linux

До Linux версии 2.4 реализация и управление потоками были полностью реализованы в режиме процесса, до Linux 2.6 ядро не поддерживало концепцию потоков, а только имитировало потоки через легковесные процессы, а пользовательский поток соответствует A потоку ядра (облегченный процесс ядра), самой большой особенностью этой модели является то, что планирование потоков выполняется ядром, в то время как другие операции с потоками (синхронизация, отмена) выполняются функциями внешней библиотеки потоков (LinuxThread). Чтобы быть полностью совместимым со стандартом Posix, в Linux 2.6 сначала было улучшено ядро и введена концепция группы потоков (по-прежнему использующая упрощенный процесс для представления потоков).С помощью этой концепции группа потоков может быть организована как процесс. , но ядро Не подготовлен специальный алгоритм планирования или определена специальная структура данных для представления потока; вместо этого поток просто рассматривается как процесс (концептуально поток), который разделяет некоторые ресурсы с другими процессами (концептуально поток). Основное изменение в реализации заключается в добавлении поля tgid в task_struct, которое представляет собой поле, используемое для представления идентификатора группы потоков. В библиотеке пользовательских потоков также используется NPTL вместо LinuxThread. Все еще используется в разных моделях планирования1 对 1Модель.

Реализация процесса заключается в вызове системного вызова fork:pid_t fork(void);, реализация потока заключается в вызове системного вызова clone:int clone(int (*fn)(void *), void *child_stack, int flags, void *arg, ...).与标准fork()По сравнению с накладными расходами потоков ядро не требует отдельной репликации пространства памяти или файловых дескрипторов и тому подобного. Это экономит много процессорного времени, так что создание потока создается в 10-100 раз чаще, чем новый процесс, который может использовать большое количество потоков, не слишком беспокоясь о ЦП или памяти. Будь то fork, vfork, kthread_create, наконец, вызов DO_FORK, а do_fork назначается ресурсам, требуемым процессу, в соответствии с различными параметрами функции.

Пул потоков

Размер пула потоков зависит от характеристик выполняемых задач и среды, в которой работает программа.Размер пула потоков должен быть настраиваемым (путем записи в файл конфигурации) или в соответствии с количеством доступных процессоров.Runtime.availableProcessors()для установки, где Ncpu представляет количество доступных ЦП, Nthreads представляет количество рабочих потоков пула потоков, а Ucpu представляет загрузку ЦП.0≤ Ucpu ≤1; W представляет время ожидания ресурса, C представляет время выполнения задачи, Rtotal представляет собой общее количество ограниченных ресурсов, а Rper представляет количество ресурсов, необходимых для каждой задачи.

Для чисто вычислительных задач ЦП, то есть задач с интенсивным использованием ЦП (вычислительных задач), которые не полагаются на блокирующие ресурсы (вызовы внешнего интерфейса) и ограниченные ресурсы (пулы потоков), размер пула потоков может быть установлен следующим образом:Nthreads = Ncpu+1.
Если задача выполняется за исключением того, что вычисление ЦП также включает некоторые вызовы внешнего интерфейса или другие созданные вычисления, размер пула потоков может быть установлен равнымNthreads = Ncpu - Ucpu -（1 + W / C）. Видно, что для случая, когда время ожидания ввода-вывода больше, чем время расчета задачи,W/CБольше 1, при условии, что загрузка ЦП равна 100%, тогдаW/CЧем больше результат, тем больше рабочих потоков требуется, потому что, если потоков недостаточно, очередь задач быстро разбухает.
Если задача зависит от некоторых ограниченных ресурсов, таких как память, дескрипторы файлов, соединения с базой данных и т. д., то пул потоков может быть установлен на максимальное значениеNthreads ≤ Rtotal/Rper.

Корутина |

COROUTINE - это легкая нить в пользовательском режиме, наиболее точное имя следует называться потоками пользовательских космических потоков (пользовательская резьба пользовательского пространства), в разных полях имеют разные имена, такие как измельчения (волокна), зеленая нить (зеленая нить) и т. Д. Устройство операционной системы Коллель COROUTINE Неверенно приложение для планирования COROUTINE для контроля, чтобы контролировать, независимо от операционной системы, эта часть планирования; нить может содержать один или несколько COROUTINE COROUTINE, имеет свой собственный стек и регистрировать контекст, когда Coroutine Cornule Handover, сохраненные регистры на Стек и тонкие линии, восстановите предыдущую транспортирующую безопасность и регистры стека во время переключения контекста обратно.

Например, ключевое слово go в Golang на самом деле отвечает за открытие Fiber и выполнение на нем логики func. И все это происходит в пользовательском режиме, а не в режиме ядра, то есть накладных расходов на ContextSwitch нет. Среди библиотек реализации сопрограмм наиболее часто используемые автором, такие как Go Routine,node-fibers,Java-QuasarЖдать.

Стек Go динамически распределяется по размеру, увеличиваясь и уменьшаясь в зависимости от объема хранимых данных. Каждая вновь созданная горутина имеет всего около 4 КБ стека. Каждый стек имеет размер всего 4 КБ, поэтому на 1 ГБ ОЗУ мы можем иметь 2,56 миллиона горутин, что является огромным улучшением по сравнению с 1 МБ на поток в Java. Golang реализует собственный планировщик, который позволяет запускать множество горутин в одном потоке ОС. Несмотря на то, что Go будет использовать те же переключатели контекста, что и ядро, он экономит много времени, не переключаясь на кольцо-0 для запуска ядра, а затем переключаясь обратно. Однако это только анализ на бумаге. Чтобы поддерживать миллионы горутин, Go должен делать более сложные вещи.

Для поддержки действительно большого параллелизма требуется еще одна оптимизация: планировать поток только тогда, когда вы знаете, что он может выполнять полезную работу. Если вы запустите много потоков, только небольшое количество потоков будет выполнять полезную работу. Go делает это, интегрируя каналы и планировщики. Если горутина ожидает на пустом канале, планировщик видит это и не запускает горутину. Go идет еще дальше и помещает большинство простаивающих потоков в потоки своей ОС. Таким образом, активные горутины (которых, как ожидается, будет намного меньше) планируются для выполнения в одном и том же потоке, в то время как миллионы спящих горутин обрабатываются индивидуально. Это помогает уменьшить задержку.

Если в Java не будут добавлены языковые функции, позволяющие планировщику наблюдать, невозможно поддерживать интеллектуальное планирование. Однако вы можете создать планировщик времени выполнения в «пространстве пользователя», который определяет, когда поток готов к выполнению работы. Это формирует основу для такого типа фреймворка, как Akka, который способен поддерживать миллионы участников.

управление параллелизмом

Когда дело доходит до многопоточных программ, часто происходят невероятные вещи: выделение переменной с кучей и стеком может привести к неожиданным результатам при последующих выполнениях, и производительность этого результата заключается в несанкционированном доступе к памяти, в результате чего содержимое памяти был изменен. Потоки в процессе совместно используют область кучи, в то время как каждый поток в процессе поддерживает свой собственный стек. На таких платформах, как Windows, разные потоки по умолчанию используют одну и ту же кучу, поэтому защита синхронизации используется при выделении памяти с помощью malloc языка C (или GlobalAlloc Windows). Если нет защиты от синхронизации, возникнет состояние гонки, когда два потока одновременно выполняют операции с памятью, что может привести к путанице в управлении памятью кучи. Например, два потока выделяют единый блок адреса памяти, неправильный указатель списка свободных мест и т. д.

Наиболее распространенными методами синхронизации процесса/потока являются блокировка мьютекса (или мьютекс), блокировка чтения-записи (rdlock), условная переменная (cond), семафор (Semaphore) и т. д.; в системе Windows критическая секция (Critical Section) и событие объекты (событие) также являются широко используемыми методами синхронизации. Подводя итог, проблема синхронизации в основном заключается в решении двух проблем атомарности и видимости/непротиворечивости.Основной метод основан на блокировках, поэтому его можно разделить на три аспекта: сериализация инструкций/управление критическими ресурсами/блокировки, согласованность данных/ видимость данных, транзакции/атомарные операции. В управлении параллелизмом мы будем рассматривать взаимодействие потоков, взаимное исключение и блокировки, параллельные контейнеры и т. д.

нить связи

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

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

Общие методы связи потоков следующие:

Pipe: Pipe — это полудуплексный метод связи.Данные могут передаваться только в одном направлении и могут использоваться только между процессами с родством.Сходство процессов обычно относится к взаимосвязи между родительскими и дочерними процессами.
Очередь сообщений: Очередь сообщений — это связанный список сообщений, хранящийся в ядре и идентифицируемый идентификатором очереди сообщений. Очередь сообщений преодолевает недостатки меньшего количества информации в сигнализации, каналы могут передавать только неформатированные потоки байтов и ограниченный размер буфера.
Семафор: семафор — это счетчик, который можно использовать для управления доступом к общим ресурсам несколькими процессами. Он часто используется в качестве механизма блокировки для предотвращения доступа других процессов к общему ресурсу, в то время как процесс обращается к ресурсу. Поэтому он в основном используется как метод синхронизации между процессами и между разными потоками в одном процессе.
Общая память: Общая память предназначена для отображения части памяти, к которой могут получить доступ другие процессы.Эта общая память создается одним процессом, но может быть доступна нескольким процессам. Общая память — это самый быстрый способ IPC, и он разработан с учетом неэффективности других методов межпроцессного взаимодействия. Он часто используется в сочетании с другими механизмами связи, такими как семафоры, для достижения синхронизации и связи между процессами.
Сокет: сокет также является механизмом межпроцессного взаимодействия, в отличие от других механизмов взаимодействия, его можно использовать для обмена данными между процессами между различными хостами.

Блокировки и мьютексы

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

Критические ресурсы

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

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

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

Пессимистическая блокировка

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

В языках программирования пессимистическая блокировка может иметь следующие недостатки:

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

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

мьютекс/эксклюзивная блокировка

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

Mutex считается наиболее часто используемой системой, усложненной блокировкой, поддержкой POSIX, C++ 11, Java и т.д. Обработка блокировки POSIX относительно распространена снаружи, C++ и Java означают, что блокировка очень интересна. C++ может использовать один AutoLock (распространенный в chromium и других проектах с открытым исходным кодом) работает как умный указатель auto_ptr в C++ 11 будет официально нормализован к std::lock_guard и std::unique_lock. Java используется сразу после синхронизируемых блоков кода синхронизации (также может быть изменен метод) в кодах синхронизации, очень гибкий. Обе реализации умело используют свои языковые функции для достижения очень элегантного способа блокировки. Конечно, они также поддерживают добавление к традиционному POSIX аналогично режиму блокировки.

повторная блокировка

Также известная как рекурсия блокировки, заключается в получении уже полученной блокировки. Отсутствие поддержки того, как поток получает то, что он получил и не был разблокирован, называется нерекурсивным или нереентерабельным. Блокировка с функцией повторного входа будет судить, является ли это тем же потоком при повторном входе.Если это так, счетчик удерживания блокировки будет равен +1 (0 означает, что он не получен потоком или блокировка снята). В C++11 одновременно поддерживаются два типа блокировок: рекурсивная блокировка std::recursive_mutex и нерекурсивная блокировка std::mutex. Две реализации мьютекса в Java, а также реализация блокировки чтения-записи поддерживают повторный вход. POSIX использует метод, называемый реентерабельными функциями, для обеспечения потокобезопасности функций, а степень детализации блокировки — вызов, а не поток.

Блокировка чтения-записи

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

Оптимистичная блокировка

По сравнению с пессимистичным блокировкой, оптимистичный механизм блокировки принимает более расслабленный механизм блокировки. По сравнению с пессимистичным блокировкой, оптимистичная блокировка предполагает, что данные не будут вызывать конфликты в целом, поэтому, когда данные представлены и обновлены, конфликт данных будет официально обнаружен. Если конфликт найден, он вернет пользовательскую ошибку. Информация, позволяющая пользователи, чтобы решить, что делать. Концепция оптимистичной блокировки, упомянутой выше, фактически объяснила свои конкретные детали реализации: в основном есть два шага: обнаружение конфликтов и обновление данных. Типичный метод реализации сравнивается и своп.

КАС и АВА

CAS — это оптимистичная технология блокировки. Когда несколько потоков пытаются использовать CAS для одновременного обновления одной и той же переменной, только один поток может обновить значение переменной, а другие потоки терпят неудачу. Неудачный поток не будет приостановлен, но будет быть заблокированным.Сообщается, что вы провалили это соревнование и можете попробовать еще раз. Операция CAS состоит из трех операндов — ячейки памяти (V), ожидаемого старого значения (A) и нового значения (B). Если значение ячейки памяти совпадает с ожидаемым исходным значением, процессор автоматически обновляет значение ячейки до нового значения. В противном случае процессор ничего не делает. В любом случае он возвращает значение в этом месте перед инструкцией CAS. CAS фактически говорит, что я думаю, что местоположение V должно содержать значение A; если это так, поместите B в это местоположение; в противном случае не меняйте местоположение, просто скажите мне, что это за местоположение сейчас. На самом деле это то же самое, что и принцип проверки конфликтов + обновления данных оптимистической блокировки.

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

Оптимистическая блокировка может гарантировать только атомарные операции над общей переменной. В приведенном выше примере во время процесса спина может быть гарантирована только атомарность переменной значения.В это время, если есть одна или несколько переменных, оптимистическая блокировка станет неэффективной, но блокировка взаимного исключения может быть легко решена независимо от количества объектов и размера частиц объекта.
Длительное вращение может привести к большим накладным расходам. Если CAS долго не работает и продолжает крутиться, это принесет много накладных расходов на ЦП.
проблема с АБА.

Основная идея CAS состоит в том, чтобы определить, было ли изменено значение памяти, сравнивая, совпадает ли значение памяти с ожидаемым значением, но эта логика суждения не является строгой.Если значение памяти изначально было A, то оно было изменяется потоком на B и, наконец, изменяется на Если возвращается A, CAS считает, что значение памяти не изменилось, но на самом деле оно было изменено другими потоками.Эта ситуация оказывает большое влияние на результаты работы сценариев, которые зависят на значения процесса. Решение состоит в том, чтобы ввести номер версии и увеличивать номер версии на единицу при каждом обновлении переменной. Частью реализации оптимистичных блокировок является решение проблемы ABA с помощью номеров версий. Каждый раз, когда оптимистическая блокировка выполняет операцию модификации данных, она приносит номер версии. Как только номер версии согласуется с номером версии данных, он можно выполнить. Измените операцию и +1 к номеру версии, в противном случае произойдет сбой. Поскольку номер версии увеличивается с каждой операцией, проблемы ABA не возникает, поскольку номер версии только увеличивается, а не уменьшается.

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

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

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

Спин-блокировки похожи на мьютексы, за исключением того, что спин-блокировки не заставляют вызывающую сторону спать. отсюда и название «спин». Его роль заключается в разрешении взаимоисключающего использования ресурса. Поскольку спин-блокировки не заставляют вызывающую программу спать, спин-блокировки намного эффективнее блокировок мьютексов. Хотя он более эффективен, чем мьютекс, он также имеет некоторые недостатки:

Спин-блокировка занимала ЦП, и она работала без получения блокировки - спина, поэтому она занимает ЦП.Если блокировка не может быть получена за очень короткий период времени, это, несомненно, снизит эффективность ЦП. .
Взаимная блокировка может быть вызвана использованием спин-блокировки, взаимоблокировка может быть вызвана рекурсивным вызовом, а взаимоблокировка также может быть вызвана вызовом некоторых других функций, таких как copy_to_user(), copy_from_user(), kmalloc() и т. д.

Спин замок более подходит для случая, когда пользователь блокировки сохраняет замок на короткое время. Именно потому, что пользователи спиновых блокировку обычно сохраняют блокировку в течение очень короткого времени, очень необходимо выбирать спину вместо сна, а эффективность спиновых замков намного выше, чем у замков Mutex. Семафоры и семафоры для чтения-записи подходят для длительного времени удержания, они вызывают спящий абонент, поэтому их можно использовать в контексте процесса, в то время как SpinLocks подходят для очень короткого времени удержания и могут использоваться в любом контексте. Если защищенный общий ресурс доступа только в контексте процесса, очень подходит для защиты общего ресурса для защиты общего ресурса. Если время доступа к общему ресурсу очень коротко, также может использоваться спинлок. Но если необходимо доступу о защищенном общий ресурс в контексте прерывания (включая нижнюю половину, обработчик прерываний и верхнюю половину, мягкое прерывание), необходимо использовать спинлок. Вытеснение недействительно во время периода удержания блокировки спина, в то время как семафор и период удержания семафора чтения и записи в семафоре можно выбрать. SpinLocks действительно нужны только в том случае, если ядро претендует или SMP (Multipressor), под одним процессором и небезопасными ядрами, все операции на Scinklocks NO-OPS. Еще одно дополнительное примечание: SpinLocks нельзя использовать рекурсивно.

MVCC

Чтобы добиться сериализации, избегая при этом проблем с существующим механизмом блокировки, мы можем использовать транзакцию многоверсионного управления параллелизмом (Multiversion concurrency control, MVCC) без механизма блокировки, задуманного как принятие. Как правило, это механизм управления параллелизмом на основе блокировки, причем указанные механизмы являются пессимистичными, но этот механизм называется оптимистическим механизмом MVCC. Это связано с тем, что механизм блокировки является превентивным, блокирует чтение и запись, блокировка записи будет читаться, когда степень детализации блокировки больше, более длительная одновременная производительность не будет хорошей; а MVCC является пост-мортемом, чтение без блокировки записи, записи или чтение препятствия, подождите, пока не будет отправлен тест, есть ли конфликт, потому что нет блокировки, поэтому читатели не будут блокировать друг друга, тем самым значительно повышая одновременную производительность. Мы можем заимствовать контроль версий исходного кода, чтобы понять MVCC, каждый может свободно читать и изменять локальный код, не блокируя друг друга, только для проверки на наличие конфликтов, когда представленная версия контроллера и подсказки сливаются. В настоящее время Oracle, PostgreSQL и MySQL уже поддерживают механизм параллелизма MVCC, но конкретная реализация различается.

Простая реализация MVCC — условное обновление, основанное на идее CAS (сравнение и замена). Обычные параметры обновления содержат только одинkeyValueSet’，Conditional UpdateНа этой основе добавляется набор условий обновленияconditionSet { … data[keyx]=valuex, … }, то есть данные обновляются до keyValueSet' только в том случае, если D удовлетворяет условиям обновления, в противном случае возвращается сообщение об ошибке. Таким образом, L формируется, как показано на следующем рисунке.Try/Conditional Update/(Try again)режим обработки:

В качестве общего примера изменения информации об учетной записи пользователя предположим, что в базе данных есть таблица с информацией об учетной записи.versionполе, текущее значение равно 1, а поле текущего баланса счета (баланс) равно 100.

Теперь оператор А читает его (версия = 1) и вычитает 50 (100-50) из баланса своего счета.
Во время работы оператора А оператор Б также считывает эту информацию о пользователе (версия=1) и списывает 20 (100-20) со своего баланса счета.
Оператор А завершает работу по модификации, увеличивает номер версии данных на единицу (версия = 2) и отправляет его в базу данных для обновления вместе с балансом после вычета счета (баланс = 50).В это время, начиная с представленной версии данных больше, чем текущая версия записи базы данных, данные удаляются. Обновить, версия записи базы данных обновляется до 2.
Оператор Б завершает операцию, а также увеличивает номер версии на единицу (версия=2) и пытается отправить данные в БД (баланс=80), но в это время при сравнении версий записей БД обнаруживается, что номер версии данных, отправленный оператором B, равен 2, текущая версия записи базы данных также равна 2, что не удовлетворяет оптимистичной стратегии блокировки, согласно которой отправленная версия должна быть больше, чем текущая версия записи для выполнения обновления. представление оператора B отклонено. Таким образом, исключается возможность перезаписи оператором B результата операции оператора A результатом модификации старых данных на основе версии=1.

Как видно из приведенного выше примера, оптимистичный механизм блокировки позволяет избежать накладных расходов на блокировку базы данных в длинных транзакциях (оператор A и оператор B не блокируют данные базы данных в процессе работы), что значительно повышает производительность при большом количестве параллелизма. . Следует отметить, что механизм оптимистической блокировки часто основан на логике хранения данных в системе, поэтому он также имеет определенные ограничения.Например, в приведенном выше примере, поскольку в нашей системе реализован механизм оптимистической блокировки, баланс пользователя обновление из внешней системы Операция не находится под контролем нашей системы, поэтому она может привести к обновлению грязных данных в базе данных.

Параллельный ввод-вывод

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

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

Тип ввода-вывода

В Unix есть пять встроенных моделей ввода-вывода: блокирующий ввод-вывод, неблокирующий ввод-вывод, модель мультиплексирования ввода-вывода, ввод-вывод, управляемый сигналом, и асинхронный ввод-вывод. С точки зрения применения типы ИО можно разделить на:

Большой/малый блок ввода-вывода: это значение относится к количеству последовательных считанных секторов, заданных в команде контроллера. Если число большое, например 64, 128 и т. д., мы можем рассматривать его как большой блок ввода-вывода; наоборот, если оно маленькое, например 4, 8, мы будем рассматривать его как небольшой блок ввода-вывода. IO На самом деле между большими и малыми блоками IO нет четких границ.
Непрерывный/случайный ввод-вывод: непрерывный ввод-вывод означает, что адрес начального сектора, заданный этим вводом-выводом, и адрес конечного сектора предыдущего ввода-вывода полностью непрерывны или не сильно отличаются друг от друга. И наоборот, если разница велика, она считается случайным вводом-выводом. Причина, по которой непрерывный ввод-вывод более эффективен, чем случайный ввод-вывод, заключается в том, что при непрерывном вводе-выводе головке практически не нужно менять дорожки, или время для смены дорожек очень короткое; а для случайного ввода-вывода, если операций ввода-вывода много, головки будут постоянно меняться, что приведет к значительному снижению эффективности.
Последовательный/параллельный ввод-вывод. Концептуально под параллельным вводом-выводом понимается выдача команды ввода-вывода на диск без ожидания его ответа, а затем выдача команды ввода-вывода другому диску. Для чередующегося RAID (LUN) его операции ввода-вывода являются параллельными, например: raid 0+1(1+0), raid5 и т. д. В противном случае это последовательный ввод-вывод.

При построении традиционных сетевых серверов режимы ввода-вывода классифицируются в соответствии с двумя стандартами: блокирующий/неблокирующий и синхронный/асинхронный.Блокировка похожа на синхронную, но разница между NIO и асинхронной заключается в том, что NIO делает упор на опрос (опрос). ), в то время как Async делает упор на уведомление (Notification). Например, в типичном однопоточном интерфейсе Socket с одним процессом блокирующий интерфейс может получить доступ к следующему соединению Socket только после закрытия предыдущего соединения Socket. Для Socket NIO серверное приложение получит специальное сообщение об ошибке «Would Block» от ядра, но оно не будет блокироваться до тех пор, пока клиент Socket не дождется остановки запроса.

Вообще говоря, в системе Linux вы можете вызвать независимыйselectилиepollметод для обхода всех считанных данных и выполнения операций записи. Для асинхронных сокетов (таких как сокеты в Windows или модель сокетов, реализованная в .Net) серверное приложение сообщит IO Framework прочитать определенные данные сокета, и IO Framework автоматически вызовет вас после считывания данных. то есть уведомить само приложение о том, что данные готовы). Взяв в качестве примера модели Reactor и Proactor в мультиплексировании ввода-вывода, неблокирующая модель требует, чтобы приложение само обрабатывало ввод-вывод, в то время как асинхронная модель использует ядро или платформу для подготовки данных в буфер, а приложение напрямую считывает данные из буфер.

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

Что касается параллельного ввода-вывода, более распространенной является так называемая проблема C10K, когда 10 000 клиентов должны подключаться к серверу и поддерживать TCP-соединение, клиент время от времени отправляет запрос на сервер, сервер получает запрос на быть своевременной обработки и возвращает результат.

мультиплексирование ввода-вывода

Мультиплексирование ввода-вывода использует механизм для мониторинга нескольких дескрипторов.Когда дескриптор готов (обычно готов к чтению или записи), он может уведомить программу о выполнении соответствующих операций чтения и записи. select, poll и epoll — все это механизмы мультиплексирования ввода-вывода. Стоит отметить, что epoll работает только для блокирующих чтение и запись операций ввода-вывода, таких как Pipe или Socket, а обычные файловые дескрипторы немедленно возвращают содержимое файла, поэтому такие функции, как epoll, не влияют на обычное чтение и запись файлов.

Сначала посмотрите на читаемые события и записываемые события: при возникновении любого из следующих условий будет сгенерировано читаемое событие сокета:

Количество байтов данных в приемном буфере сокета больше или равно размеру минимальной отметки приемного буфера сокета;
Половина сокета для чтения закрыта (то есть получен FIN), и операция чтения на таком сокете вернет 0 (то есть вернет EOF);
Сокет является слушающим сокетом, и количество завершенных соединений не равно 0;
В этом сокете есть ожидающая ошибка, и чтение из такого сокета вернет -1.

Событие, доступное для записи сокета, генерируется, когда происходит любое из следующих событий:

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

select, poll, epoll по сути являются синхронным вводом-выводом, потому что все они должны отвечать за чтение и запись после того, как будут готовы события чтения и записи, то есть процесс чтения и записи заблокирован, в то время как асинхронный ввод-вывод не требует сам отвечает за чтение и запись Реализация асинхронного ввода-вывода отвечает за копирование данных из ядра в пространство пользователя. select сам по себе является опросом и без сохранения состояния.Каждый вызов должен копировать набор fd из пользовательского режима в режим ядра.Эти накладные расходы будут очень большими, когда есть много fds. epoll обрабатывает соединения триггерным образом, поддерживает неограниченное количество дескрипторов, а производительность не снижается по мере увеличения количества дескрипторов.

метод	Количественные ограничения	обработка соединения	операция памяти
select	Количество дескрипторов ограничено FD_SETSIZE в ядре, которых всего 1024; перекомпиляция ядра меняет значение FD_SETSIZE, но производительность не может быть оптимизирована	Каждый вызов select будет линейно сканировать состояние всех дескрипторов.После завершения select пользователь также линейно сканирует массив fd_set, чтобы узнать, какие дескрипторы готовы (O(n))	Каждый раз, когда вызывается select, дескрипторы fd копирования памяти и другая информация выполняются в пространстве пользователя и пространстве ядра.
poll	Используйте структуру pollfd для хранения fd, преодолевая ограничение на количество дескрипторов в select.	Аналогично выбору метода сканирования	Необходимо скопировать массив pollfd в пространство ядра, а затем поочередно сканировать состояние fd.Общая сложность по-прежнему O(n), и производительность сервера будет быстро падать в случае большого параллелизма.
epoll	Список fd, соответствующий Socket в этом режиме, хранится массивом, и его размер не ограничен (по умолчанию 4k)	На основе режима отражения, предоставляемого ядром, при наличии активного сокета ядро обращается к обратному вызову сокета, не проходя через опрос.	epoll использует совместное использование памяти вместо копирования памяти при передаче сообщений между ядром и пользовательским пространством, что также делает epoll более эффективным, чем опрос и выбор