이전 장에서는 배열 양식을 사용하여 ArrayBlockingqueue로 구현 된 차단 큐를 설명했습니다.
배열의 길이는 생성 할 때 결정해야합니다. 배열 길이가 작 으면 ArrayBlockingqueue 큐가 쉽게 차단됩니다. 배열 길이가 크면 쉽게 메모리를 낭비합니다.
큐 데이터 구조는 링크 된 목록의 형태에 자연스럽게 적합하며 LinkedBlockingqueue는 링크 된 목록을 사용하여 구현 된 차단 큐입니다.
1. 링크 된 목록 구현
1.1 노드 내부 클래스
/ *** 링크 된 목록의 노드는 또한 일방 통행 링크 목록*/ 정적 클래스 노드 <e> {e item; // 링크 된 목록 노드의 다음 노드를 가리 킵니다. 노드 (e x) {item = x; }}데이터를 저장하는 변수 E가 있으며 다음 노드를 가리키는 변수 다음 참조가 있습니다. 가장 간단한 일원 목록을 구현할 수 있습니다.
1.2 링크 목록을 구현하는 방법
/ *** 큐 헤드의 다음 지점,이 노드는 데이터*/ 과도 노드 <e> 헤드를 저장하지 않습니다. / *** 대기열 꼬리 노드*/ 개인 과도 노드 <E> 마지막;
링크 된 목록을 구현하려면 두 가지 변수가 있어야합니다. 하나는 링크 된 목록의 헤드를 나타내고 다른 하나는 링크 된 목록의 마지막을 나타냅니다. Head와 Last는 LinkedBlockingqueue 객체가 생성 될 때 초기화됩니다.
last = head = 새 노드 <e> (null);
여기에는 작은 트릭이 사용됩니다. 링크 된 목록의 헤드 노드는 데이터를 저장하지 않습니다. 다음 노드는 링크 된 목록에 첫 번째 데이터를 진정으로 저장하는 것을 가리 킵니다. 링크 된 목록 끝의 마지막은 실제로 마지막 데이터를 링크 된 목록에 저장합니다.
1.3 노드 삽입 및 삭제
/ *** 대기열의 꼬리에 노드를 삽입*/ private void enqueue (node <e> 노드) {// putlock.isheldbycurrentthread (); // 현재 스레드는 Putlock Lock을 얻어야합니다. // 원래 큐 테일 노드의 다음 참조를 새 노드 노드에 가리킨 다음 큐의 마지막 테일 노드로 노드 노드를 설정합니다. // 큐의 꼬리에 노드를 삽입하는 것을 알 수 있습니다. }링크 된 목록의 끝에 노드를 삽입하는 것은 매우 간단합니다. 원래 큐의 다음 노드를 새 노드 노드로 마지막으로 가리키 다음 큐 끝의 마지막 노드에 새 노드 노드를 할당하십시오. 이를 통해 새 노드를 삽입 할 수 있습니다.
// 큐 헤드 노드를 제거하고 삭제 된 노드 데이터를 반환 개인 e dequeue () {// assert takelock.isheldbycurrentthread (); // 현재 스레드는 Takelock Lock을 얻었어야합니다. // assert head.item == null; 노드 <e> h = 헤드; // 큐의 첫 번째 요소의 데이터는 첫 번째 노드 노드 <e> first = h.next에 저장됩니다. h.next = h; // GC를 도와주세요 // 새 헤드 값을 설정하는 것은 첫 번째 노드를 삭제하는 것과 같습니다. 헤드 노드 자체가 데이터 헤드 = 먼저 저장하지 않기 때문입니다. // 큐 헤더의 데이터 e x = first.Item; // 원래 데이터를 먼저 제거합니다 .Item = null; 반환 x; }헤드는 헤더가 아니라 헤더의 다음 지점이므로 헤더를 삭제하는 것은 매우 간단합니다. 헤드 .next를 헤드에 할당 한 다음 원래 Head.next 노드의 데이터를 반환하는 것이 매우 간단합니다.
삭제할 때 링크 된 목록이 비어있는 상황에주의하십시오. head.next 값은 eNqueue 방법을 사용하여 추가됩니다. Head.next == 마지막으로 마지막 요소가 삭제되었음을 의미합니다. head.next == null 일 때 링크 된 목록이 이미 비어 있으므로 삭제할 수 없습니다. Dequeue 방법이 호출되는 곳에서 판단이 이루어 졌기 때문에 여기에는 판단이 없습니다.
2. 동기식 잠금 장치 재 렌트 링크 및 조건
차단 대기열이 차단되고 대기열이 비어 있고 대기열이 가득 차면 기다려야하므로 두 가지 조건이 자연스럽게 필요합니다. 다중 스레드 동시성의 안전을 보장하기 위해서는 동기화 잠금이 필요합니다. 이것은 ArrayBlockingqueue에서 언급되었습니다.
여기서 우리는 LinkedBlockingqueue에 대한 다양한 것들에 대해 이야기 할 것입니다.
/ ** 큐 작업을 삽입하는 동시성 문제를 처리하는 데 사용되는 독점 잠금, 즉 PUT 및 제공*/ Private Final ReintrantLock Putlock = New ReintrantLock (); / ** 대기열이 충족되지 않는 조건 조건, Putlock Lock*/ Private Final Condition NoteFull = putlock.newCondition ()에 의해 생성됩니다. / ** 큐 헤드 작업을 삭제하는 동시성 문제를 처리하는 데 사용되는 독점 잠금, 즉 테이크 및 폴링 작업*/ 개인 최종 재 렌트 링크 락 takelock = 새로운 reintrantlock (); / ** 대기열이 비어 있지 않다는 조건 조건은 Takelock Lock에 의해 생성 된 개인 최종 조건을 사용합니다*/ 개인 최종 조건 notempty = takelock.newcondition ();
2.1 퍼 락과 Takelock
우리는 두 개의 자물쇠가 사용되는 것을 발견했습니다.
위의 진술에 따르면, 요소를 동시에 삽입 및 삭제하는 작업이있을 수 있으므로 문제가 없을 것입니까?
자세히 분석하겠습니다. 대기열의 경우 작업은 세 가지 유형으로 나뉩니다.
따라서 Putlock Lock을 사용하여 마지막 변수를 안전하게 유지하고 Takelock 잠금을 사용하여 헤드 변수를 안전하게 유지하십시오.
대기열의 요소 수와 관련된 모든 카운트 변수에 대해 AtomicInteger는 동시성 보안 문제를 보장하는 데 사용됩니다.
/ ** 대기열의 요소 수는 동시성 보안 문제를 보장하기 위해 여기에서 AtomicInteger 변수를 사용하십시오*/ 개인 최종 AtomicInteger count = new atomicinteger ();
2.2 공증과 무의미한
2.3 제어 프로세스
요소를 삽입 할 때 :
요소를 삭제할 때 :
또한 잠금 장치를 얻을 때 신호와 대기 방법을 호출해야합니다. 따라서 Signalnotempty 및 SignalNotfull 메소드가 있습니다.
/*** 무의미한 조건에서 대기 대기, 즉 큐 헤더를 제거 할 때 비어 있고 기다려야하는 스레드가 대기 중입니다. * 조건의 신호 메소드를 호출하려면 해당 잠금 장치를 얻어야합니다. Takelock.lock () 메소드는 여기에서 호출됩니다. * 요소가 큐에 삽입되면 (예 : Put 또는 Offer 조작) 대기열이 분명히 비어 있지 않으며이 방법이 호출됩니다. */ private void signalnotempty () {Final ReintrantLock takelock = this.takelock; takelock.lock (); try {notempty.signal (); } 마침내 {takelock.unlock (); }} /*** 무의미한 조건에서 대기하는 스레드를 깨우십시오. * 조건의 신호 메소드를 호출하려면 해당 잠금 장치를 얻어야하므로 Putlock.lock () 메소드가 여기에서 호출됩니다.* 요소 (예 : 테이크 또는 폴링 작동)가 큐에서 삭제되면 대기열이 확실히 불만족 스럽고이 방법을 호출합니다. */ private void signalnotfull () {Final ReintrantLock Putlock = this.putlock; putlock.lock (); try {notfull.signal (); } 마침내 {putlock.unlock (); }}3. 요소 방법을 삽입하십시오
Public Void Put (e e) 던지기 중간 exception {if (e == null) 새 nullpointerexception (); // 삽입 전 요소 수를 기록합니다. int c = -1; // 새 노드 노드를 만듭니다 <e> 노드 = 새 노드 <e> (e); 최종 재진입 락 Putlock = this.putlock; 최종 Atomicinteger count = this.count; putlock.lockinterruptibly (); {// 큐가 가득 찼음을 나타냅니다. 그러면 현재 스레드를 기다리려면 (count.get () == 용량) {notfull.await (); } // 새 요소 eNqueue (노드) 삽입; // 현재 큐의 요소 수에 1을 추가하고 1을 추가하기 전에 요소 수를 반환합니다. // c + 1 <용량은 큐가 가득 차 있지 않음을 의미하고 삽입 작업을 기다리는 스레드가 (c + 1 <용량) idfull.signal (); } 마침내 {putlock.unlock (); } // c == 0은 큐가 삽입하기 전에 큐가 비어 있음을 의미합니다. 대기열이 배치되는 요소에 비어 있으면 // 삭제 대기 대기 스레드를 깨우십시오. // Takelock 잠 자주 획득을 방지하고 (c == 0) signalnotempty (); }PUT 방법을 예로 들어 보면 일반적인 프로세스는 앞에서 소개 한 것과 동일합니다. 다음은 매우 이상한 코드입니다. 요소가 삽입되면 대기열이 가득 찼다는 것을 알게되면 indefull.signal ()을 호출하여 삽입을 기다리는 스레드를 깨우십시오.
모두가 매우 혼란 스럽습니다. 일반적으로,이 방법은 요소를 삭제할 때 큐가 아래에 부족해야하기 때문에 삭제를 기다리는 스레드를 깨우려면 큐가 부적절해야하기 때문에 삭제 요소 (시리즈 메소드를 가져 가라)에 배치해야합니다.
신호 메소드를 호출 할 때 해당 잠금 장치를 먼저 얻어야하므로 주로 수행됩니다. 테이크 시리즈 방법에 사용 된 잠금 장치는 Takelock입니다. notefull.signal () 메소드를 호출하려면 먼저 퍼 락 잠금을 얻어야합니다. 이로 인해 성능이 줄어들어 다른 방법이 사용됩니다.
4. 큐 헤더 요소를 삭제합니다
public e take ()가 중단 된 exception {e x; int c = -1; 최종 Atomicinteger count = this.count; 최종 재진입 락 takelock = this.takelock; takelock.lockinterruptibly (); try {// 큐가 비어 있음을 의미하면 현재 스레드가 대기하기 위해서는 notempty.await 메소드를 호출해야합니다 (count.get () == 0) {notempty.await (); } // 큐 헤더 요소를 삭제하고 반환 x = dequeue (); // 현재 대기열의 수를 반환 한 다음 큐 수를 하나의 c = count.getAndEcrement ()로 빼냅니다. // c> 1은 큐가 비어 있지 않다는 것을 의미하므로 (c> 1) notempty.signal (); } 마침내 {takelock.unlock (); } /*** c == 용량은 삭제 작업 전에 큐가 가득 찼음을 의미합니다. * 전체 대기열에서 요소가 삭제 될 때만 삽입 대기 대기 스레드를 깨우십시오. 반환 x; }notempty.signal () 메소드가 호출되는 이유는 삽입 요소 메소드에서 설명을 비교하십시오.
5. 큐 헤더 요소를 봅니다
// 큐 헤더 요소보기 public e peek () {// 큐가 비어 있고 (count.get () == 0) return null; 최종 재진입 락 takelock = this.takelock; takelock.lock (); {// 큐 헤더 노드를 가져옵니다. 첫 노드 <e> first = head.next; // first == null은 큐가 비어 있음을 의미합니다. else // 큐 헤더 요소를 반환합니다. } 마침내 {takelock.unlock (); }}헤드 노드가 포함 된 큐 헤더 요소를보고 Takelock 잠금을 사용해야합니다.
VI. 다른 중요한 방법
6.1 제거 (개체 O) 메소드
// 대기열에서 지정된 요소를 제거하십시오 o public boolean remove (object o) {if (o == null) false를 반환합니다. // 목록 헤더 요소를 삭제하지 않기 때문에 두 변수 헤드와 마지막이 관련되어 있습니다. // putlock 및 takelock은 Fulliclock ()을 잠겨 있어야합니다. 시도 {// 전체 큐를 가로 지르고 P는 현재 노드를 나타내고, 트레일은 현재 노드의 이전 노드를 나타냅니다. // 일회용 링크 목록이기 때문에 두 개의 노드를 기록해야합니다 (Node <E> Trail = Head, P = Trail.Next; P! = NULL; TRAIL = P, P = P = P.NEXT). (O.equals (p.item)) {Unlink (p, trail); 진실을 반환하십시오. }} 거짓을 반환합니다. } 마침내 {fulluunlock (); }}목록에서 지정된 요소를 삭제하십시오. 삭제 된 요소가 반드시 목록의 헤드에 있지 않기 때문에 두 개의 변수 헤드와 마지막이있을 수 있으므로 동시에 퍼팅과 타클 록 잠금 장치를 모두 사용해야합니다. 일방 통행 링크 목록이므로 현재 노드 P를 삭제할 수 있도록 이전 노드를 기록하려면 보조 변수 트레일이 필요합니다.
6.2 Unlink (Node <E> P, Node <E> 트레일) 메소드
// 현재 노드 P를 삭제하고 트레일은 p void Unlink의 이전 노드를 나타냅니다 (node <e> p, node <e> trail) {// 현재 노드의 데이터를 null p.item = null로 설정합니다. // 이것은 노드 p 트레일을 삭제합니다 .next = p.next; // 노드 P가 큐의 마지막 마지막이고 삭제 된 경우 트레일을 마지막 if (last == p) last = trail으로 설정하십시오. // 원래 대기열이 가득 찬 경우 요소의 수를 하나씩 빼면 Notefull.Signal () 메소드를 호출하십시오. 실제로, 이것은 (count.getAndEcrement () == 용량) notefull.signal (); }링크 된 목록에서 노드 P를 삭제하려면 P의 이전 노드 트레일의 다음 노드 트레일을 다음 노드 P의 다음 노드로 만 가리킬 필요가 있습니다.
위는이 기사의 모든 내용입니다. 모든 사람의 학습에 도움이되기를 바랍니다. 모든 사람이 wulin.com을 더 지원하기를 바랍니다.