В предыдущей главе мы представили блокирующую очередь блокировки. Ниже мы представляем его обычно используемое класс реализации ArrayBlockingQueue.
1. Используйте массивы для внедрения очередей
Из -за особых требований структуры данных очереди, естественно, подходит для реализации в форме связанного списка. Две переменные используются для записи заголовка и конца связанного списка соответственно. При удалении или вставке очереди просто измените заголовок или конец связанного списка. Более того, связанный список связан с справочным способом, поэтому его емкость почти не ограничена.
Итак, как использовать массивы для реализации очередей, нам нужны четыре переменные: объект [] массив для хранения элементов в очереди, Headindex и Tailindex. Запишите очередь и хвост, и подсчет записывает количество очередей.
Здесь используется очень умный способ. Мы знаем, что когда элемент вставлен в очередь, он занимает позицию в массиве. Когда элемент удаляется, положение массива на самом деле является свободным, что указывает на то, что в этом положении можно вставить новый элемент.
Поэтому, прежде чем мы вставим новый элемент, мы должны проверить, заполнена ли очередь, и прежде чем удалить элемент, мы должны проверить, пуста ли очередь.
2. Важные переменные члена в ArrayBlockingQueue
/ ** Хранить элементы в очереди*/ final Object [] элементы; / ** Положение головы очереди*/ int takeindex; / ** Положение хвоста очереди*/ int putindex; / ** Количество элементов в текущей очереди*/ int count; / ** Используется для обеспечения безопасности многопоточных общих переменных*/ окончательный блокировка повторного разряда; / ** Когда очередь пуст, будет вызван метод ожидания Notempty, чтобы дать текущий поток ждать*/ частное окончательное условие notempty; / ** Когда очередь заполнена, будет вызовен метод ожидания, в результате чего текущий поток ждать*/ частное окончательное условие заметно;
Существует больше блокировки, нотмпти и заметных переменных для реализации многопоточных условий безопасности и условий ожидания потоков. Как они работают?
2.1 Роль блокировки
Поскольку ArrayBlockQueue работает в нескольких потоках, при изменении переменных элементов, таких как элементы, TakeIndex, Putindex и Count, необходимо рассмотреть проблемы с многопоточной безопасностью. Поэтому здесь используется эксклюзивная блокировка блокировки для обеспечения безопасности параллельных операций.
2.2 Роль Notempty и заметно
Поскольку блокирующие очереди должны быть реализованы, когда очередь пуст или очередь заполнена, очередь чтение или операция вставки должна ждать. Таким образом, мы подумали о объекте «Состояние» в рамках параметра и используем его для его управления.
В AQS мы вводим роль этого класса:
3. Добавить метод элемента
3.1 Добавить (e E) и предложить (E E) Методы:
// Вызовите метод в родительском классе AbstractQueue. public boolean add (e e) {// реализовать if (Предложение (e)) вернуть true; иначе выбросить новое allodalStateException ("queue Full"); } // Добавить новый элемент в конце очереди. Возврат true означает, что дополнение является успешным, false означает, что добавление не удалось, и никакое исключение не добавлено в общедоступное логическое предложение (e E) {checknotnull (e); окончательный reentrantlock lock = this.lock; // Использование блокировки, чтобы убедиться, что многопоточная модификация атрибутов элементов lock.lock (); Попробуйте {// очередь полна, а добавление элементов не удается, вернуть ложь. if (count == items.length) вернуть false; else {// вызовите метод Enqueue, чтобы вставить элемент в очередь Enqueue (e); вернуть истину; }} наконец {lock.unlock (); }}Метод добавления реализован путем вызова метода предложения. В методе предложения необходимо сначала определить, заполнена ли очередь. Если он заполнен, он непосредственно вернет ложь, не блокируя текущий поток. Если вы не удовлетворены, вызовите метод Enqueue, чтобы вставить элемент в очередь.
ПРИМЕЧАНИЕ. Использование lock.lock () здесь гарантирует, что только один поток изменяет переменные элемента одновременно для предотвращения одновременных задач работы. Хотя он также будет блокировать текущий поток, он не является условным ожиданием, это просто потому, что блокировка удерживается другими потоками, а время работы метода в ArrayBlockingQueue не длинное, что эквивалентно блокированию потока.
3.2 Поместите метод
// Добавить новый элемент в конце очереди. Если очередь заполнена, текущий поток будет ждать. Ответ на исключение прерывания public void put (e) бросает прерывания ErruptedException {checknotnull (e); окончательный reentrantlock lock = this.lock; // Использование блокировки, чтобы убедиться, что многопоточные точки модифицируют безопасность атрибутов участника lock.lockEntertible (); Попробуйте {// Если очередь полна, вызовите метод natfull.await (), чтобы дать текущему потоку подождать, пока очередь не будет полна, в то время как (count == item.length) natufull.await (); // Вызовите метод Enqueue, чтобы вставить элемент в очередь Enqueue (e); } наконец {lock.unlock (); }}Общий процесс метода предложения такой же, как и метод предложения. Однако, когда очередь заполнена, будет вызван метод natfull.await (), чтобы сделать текущий блок резьбы и подождать, пока очередь не будет удалена другими потоками. Когда очередь неудовлетворена, поток ожидания будет пробуждена.
3.3 Метод предложения (E E, длительный тайм -аут, единица времени UNIT)
/*** Добавьте новый элемент в конце очереди. Если в очереди нет места, текущий поток будет ждать. * Если время ожидания превышает тайм -аут, то false возвращается, указывая на то, что добавление не удалось*/ public boolean предложение (e, длительный тайм -аут, время Unit), бросает прерывания {checknotnull (e); // Рассчитать значение времени максимального ожидающего общего нано нано нанос = unit.tonanos (тайм -аут); окончательный reentrantlock lock = this.lock; // Использование блокировки, чтобы убедиться, что многопоточная модификация атрибутов члена lock.lockErenterbultible (); Try {// очередь полна, в то время как (count == items.length) {// nanos <= 0 означает, что максимальное время ожидания достигнуто, поэтому нет необходимости ждать дольше. Вернуть ложь, указывая на то, что добавление не удалось. if (nanos <= 0) вернуть false; // Вызов метод natfull.awaitnanos (Nanos), время наноса тайм -аута будет автоматически пробуждено. // Если он проснулся заранее, то оставшееся время возвращается nanos = natufull.awaitnanos (nanos); } // Вызовите метод Enqueue, чтобы вставить элемент в очередь Enqueue (e); вернуть истину; } наконец {lock.unlock (); }}Общий поток метода PUT совпадает с методом PUT, он просто вызывает метод altufull.Awaitnanos (Nanos), чтобы дать текущий потоковой сигнал ожидание и установить время ожидания.
4. Удалить метод элемента
4.1 METHONE EXEMPER () и OLL ():
// Вызовите метод в родительском классе AbstractQueue. public e Remove () {// реализация, вызывая опрос e x = опрос (); if (x! = null) вернуть x; иначе бросить новое noshelementexception (); } // Удалить первый элемент очереди (то есть заголовок очереди) и вернуть его. Если очередь пуста, она не бросает исключение, но возвращает NULL. public e опросом () {окончательный reentrantlock lock = this.lock; // Использование блокировки, чтобы убедиться, что многопоточная модификация атрибутов элементов lock.lock (); Попробуйте {// Если count == 0, а список пуст, вернуть NULL. В противном случае вызовите метод Dequeue, чтобы вернуть элемент заголовка списка (count == 0)? null: dequeue (); } наконец {lock.unlock (); }}Метод удаления реализуется путем вызова метода опроса (). В методе опроса (), если список пуст, он возвращает NULL, в противном случае метод Dequeue вызывается, чтобы вернуть элемент заголовка списка.
4.2 Take () Метод
/*** Верните и удалите первый элемент очереди. Если очередь пуст, передняя поток будет ждать. Исключение прерывания ответа*/ public e take () Throws treamptenException {final Reentrantlock lock = this.lock; // Использование блокировки, чтобы убедиться, что многопоточные точки модифицируют безопасность атрибутов участника lock.lockEntertible (); Попробуйте {// Если очередь пуста, вызовите метод notempty.await (), чтобы дать текущему потоку подождать. // до тех пор, пока другая потока не вставит элементы в очередь, поток будет пробуждена. while (count == 0) notempty.await (); // Вызовите метод Dequeue, чтобы вернуть элемент заголовка списка return dequeue (); } наконец {lock.unlock (); }}Когда метод take () пуст, текущий поток должен ждать, пока другой потоко не вставит новый элемент в очередь, и поток будет пробужден.
4.3 Метод опроса (длительный тайм -аут, Unit Unit)
/*** Верните и удалите первый элемент очереди. Если очередь пуст, передняя поток будет ждать. * Если время ожидания превышает тайм -аут, то FALSE возвращается, чтобы указать, что элемент не удастся*/ Public E опроса (длительный тайм -аут, единица TimeUnit), бросает прерывания. окончательный reentrantlock lock = this.lock; // Использование блокировки, чтобы убедиться, что многопоточная модификация атрибутов члена lock.lockErenterbulal (); Попробуйте {// очередь пуста, в то время как (count == 0) {// nanos <= 0 означает, что максимальное время ожидания достигнуто, поэтому больше не нужно ждать, вернуть ноль. if (nanos <= 0) вернуть null; // Вызовите метод notempty.awaitnanos (nanos), чтобы заставить поток расписания подождать и установить время ожидания. nanos = notempty.awaitnanos (Nanos); } // Вызовите метод Dequeue, чтобы вернуть элемент заголовка списка return dequeue (); } наконец {lock.unlock (); }}Так же, как метод Take () метод, он просто называется методом Awaitnanos (Nanos), чтобы дать текущий поток ждать и установить время ожидания.
5. Методы для просмотра элементов
5.1 Element () и Peek () Методы
// Вызовите метод в родительском классе AbstractQueue. public e element () {e x = peek (); if (x! = null) вернуть x; иначе бросить новое noshelementexception (); } // Просмотреть элементы заголовка очереди public e peek () {final Reentrantlock lock = this.lock; // Использование блокировки, чтобы убедиться, что многопоточная модификация атрибутов элементов lock.lock (); try {// вернуть элемент текущего заголовка очереди returnate (takeindex); // null, когда очередь пуст} наконец {lock.unlock (); }}VI Другие важные методы
6.1 Методы Enqueue и Dequeue
// Вставьте элемент x в хвост очереди Private void enquue (e x) {// assert lock.getholdCount () == 1; // утверждать элементы [putindex] == null; // текущий элемент позиции PutIndex должен быть NULL FOULANT EACTION [] elects = this.Items; элементы [putindex] = x; // Если PUTINDEX равен items.length, сбросить PUTINDEX до 0 IF (++ putIndex == elects.length) putIndex = 0; // Добавить один счет ++ в количество очередей; // Поскольку элемент вставлен, текущая очередь определенно не пуста. Затем разбудите поток, ожидающую условия Notempty NoteMpty.Signal (); } // Удалить элемент заголовка очереди и вернуть его private e dequeue () {// assert lock.getholdCount () == 1; // Утверждать элементы [takeIndex]! = null; Окончательный объект [] items = this.items; // Получить элемент текущего заголовка очереди @suppresswarnings ("unchecked") e x = (e) элементы [takeedIndex]; // Установите позицию заголовка текущей очереди на нулевые элементы [takeIndex] = null; if (++ takeIndex == item.length) takeIndex = 0; // минус количество очередей по одному счету ...; if (itrs! = null) itrs.elementdequed (); // Поскольку элемент удален, очередь определенно не удовлетворена, поэтому разбудите поток, ожидающую в соответствии с заметным условием natfull.signal (); возврат x; }Эти два метода представляют собой, вставляя элементы и удаляя элементы из очереди соответственно. И они хотят разбудить ожидающую ветку. После вставки элемента очередь не должна быть пустой, поэтому поток, ожидающий в соответствии с условием Notempty, должна быть пробуждена. После удаления элемента очередь должна быть неудовлетворенной, поэтому поток, ожидающий приватного условия, должна быть пробуждена.
6.2 Удалить (объект o) Метод
// Удалить элемент объекта o в очереди и удалить не более одного публичного логического удаления (объект o) {if (o == null) вернуть false; Окончательный объект [] items = this.items; // Использование блокировки, чтобы обеспечить безопасность многопоточной модификации атрибутов члена Окончательный reentrantlock lock = this.lock; lock.lock (); Попробуйте {// Удалить только тогда, когда есть значение в очереди. if (count> 0) {// Следующая позиция в конце очереди окончательного int putindex = this.putindex; // положение заголовка очереди int i = takeindex; do {// Элемент текущего положения такой же, как у удаленного элемента if (o.equals (items [i])) {// delete element i position removeat (i); // вернуть истинную версию верно; } if (++ i == item.length) i = 0; // Когда я == putindex означает, что все элементы были пересечены} while (i! = Putindex); } вернуть false; } наконец {lock.unlock (); }} Удалите указанный объект O из очереди, затем вы должны пройти очередь и удалить первый элемент, который совпадает с объектом o. Если в очереди нет элемента объекта o, верните False, чтобы удалить неудачу.
Вот два момента, чтобы отметить:
Как пройти очередь - это пересечь от головы очереди до конца очереди. Это зависит от двух переменных, которые Takeindex и Putindex.
Почему объект [] элементы = this.items; Этот код не помещен в блок синхронной блокировки блокировки. Предметы являются переменными участниками. Когда будет так много потоков, не будет ли проблем с параллелизмом?
Это связано с тем, что элементы являются эталонными переменными, а не основными типами данных, а наши операции вставки и удаления в очередях предназначены для этого массива элементов, а ссылка на массив не изменяется. Поэтому в коде блокировки элементы получат последние изменения по другим потокам. Но если int putindex = this.putindex; Метод блокирует кодовый блок снаружи, возникнет проблема.
Метод Removeat (final int RemoveIndex)
// Удалить элемент в очередь removeIndex position void Removeat (окончательный int removeIndex) {// assert lock.getholdCount () == 1; // утверждать элементы [removeIndex]! = null; // ASSERT removeIndex> = 0 && removeIndex <ement.length; Окончательный объект [] items = this.items; // это означает, что гораздо проще удалить элемент в качестве заголовка списка, который похож на процесс метода Dequeue if (removeIndex == takeIndex) {// Удалить элемент в элементах положения removeIndex [TakeDIndex] = null; // Когда конец массива вам нужно перейти в позицию заголовка массива, если (++ takeindex == item.length) takeIndex = 0; // минус количество очередей по одному счету ...; if (itrs! = null) itrs.elementdequed (); } else {// an "интерьер" удалить окончательный int putindex = this.putindex; для (int i = removeIndex ;;) {int next = i + 1; if (next == items.length) next = 0; // Конец очереди еще не достиг конца очереди, тогда элемент в следующей позиции перезаписан элементом в предыдущей позиции, если (Далее! i = Далее; } else {// Установить хвостовой элемент очереди NULLE Items [i] = null; // сбросить значение putindex this.putindex = i; перерыв; }} // Уменьшите количество очередей по счету-; if (itrs! = null) itrs.removedat (removeIndex); } // Поскольку элемент удален, очередь определенно не удовлетворена, поэтому разбудите поток, ожидающий в соответствии с заметным условием natfull.signal (); }Удалить элементы в указанном месте в очереди. Следует отметить, что массив после удаления все еще может поддерживать форму очереди, которая разделена на две ситуации:
Выше всего содержание этой статьи. Я надеюсь, что это будет полезно для каждого обучения, и я надеюсь, что все будут поддерживать Wulin.com больше.