前の章では、ブロッキングキューブロッキングキューを紹介しました。以下に、一般的に使用される実装クラスArrayBlockingQueueを紹介します。
1.配列を使用してキューを実装します
キューのデータ構造の特別な要件があるため、リンクされたリストの形式で実装するのに自然に適しています。 2つの変数を使用して、それぞれリンクリストのヘッダーと最後を記録します。キューを削除または挿入するときは、リンクリストのヘッダーまたは端を変更するだけです。さらに、リンクされたリストは参照方法でリンクされているため、その容量はほとんど無制限です。
したがって、配列を使用してキューを実装する方法は、4つの変数が必要です。オブジェクト[]配列はキューに要素を保存し、headindexとtailindexはキューヘッドとテールを記録し、キューの数を記録します。
ここでは非常に賢い方法が使用されています。要素がキューに挿入されると、配列に位置を占めることがわかります。要素が削除されると、配列の位置は実際には自由であり、この位置に新しい要素を挿入できることを示します。
そのため、新しい要素を挿入する前に、キューがいっぱいかどうかを確認する必要があり、要素を削除する前に、キューが空であるかどうかを確認する必要があります。
2.配列ブロッキングキューの重要なメンバー変数
/ **要素をキューに保存*/ finalオブジェクト[]アイテム。 / **キューヘッドの位置*/ int takeIndex; / **キューテールの位置*/ int putindex; / **現在のキューの要素の数*/ intカウント。 / **マルチスレッドの共有変数のセキュリティを確保するために使用されます*/ final reentrantlockロック。 / **キューが空の場合、Notemptyの待機方法が呼び出され、現在のスレッドが待機します*/プライベート最終条件Notempty; / **キューがいっぱいになった場合、著名な待機方法が呼び出され、現在のスレッドが待機します*/プライベート最終条件は著しくありません。
マルチスレッドの安全性とスレッドの待機条件を実装するための、より多くのロック、Notempty、および顕著な変数があります。それらはどのように動作しますか?
2.1ロックの役割
ArrayBlockingQueueは複数のスレッドで動作するため、アイテム、TakeIndex、Putindex、Countなどのメンバー変数を変更する場合、マルチスレッドの安全性の問題を考慮する必要があります。したがって、ここでは、ロック排他的ロックが同時操作の安全性を確保するために使用されます。
2.2 Notemptyと著名な役割
キューをブロックする必要があるため、キューが空の場合、またはキューがいっぱいの場合、キューの読み取りまたは挿入操作が待機する必要があります。そのため、Concurrencyフレームワークの下で条件オブジェクトを考え、それを使用して制御します。
AQSでは、このクラスの役割を紹介します。
3.要素メソッドを追加します
3.1追加(e e)と提供(e e)メソッド:
// AbstractQueueの親クラスのメソッドを呼び出します。 public boolean add(e e){// if(offer(e))return true;それ以外の場合は、新しいIllegalStateException( "queue full")を投げます。 } //キューの最後に新しい要素を追加します。 return trueは、追加が成功することを意味し、falseは追加が失敗したことを意味し、例外はパブリックブールのオファー(e e){checknotnull(e); final reentrantlock lock = this.lock; //ロックを使用して、メンバー属性のマルチスレッド変更lock.lock()を確認することを確認してください。 try {//キューがいっぱいで、要素の追加が故障し、falseを返します。 if(count == items.length)falseを返します。 else {// enqueueメソッドを呼び出して、要素をキューエンキュー(e)に挿入します。 trueを返します。 }}最後に{lock.unlock(); }}ADDメソッドは、オファーメソッドを呼び出すことによって実装されます。オファー方法では、最初にキューがいっぱいかどうかを判断する必要があります。いっぱいの場合、現在のスレッドをブロックせずに直接Falseを返します。満足していない場合は、Enqueueメソッドを呼び出して、要素をキューに挿入します。
注:lock.lock()を使用すると、並行操作の問題を防ぐために、1つのスレッドがメンバー変数を同時に変更することを保証します。また、現在のスレッドをブロックしますが、条件付きの待機ではありません。ロックが他のスレッドによって保持されているからといって、アレイブロッキングキューのメソッド操作時間は長くはありません。これは、スレッドをブロックしないことと同等です。
3.2 PUTメソッド
//キューの最後に新しい要素を追加します。キューがいっぱいの場合、現在のスレッドが待機します。割り込み例への応答public void put(e e)throws arturtedexception {checknotnull(e); final reentrantlock lock = this.lock; //ロックを使用して、マルチスレッドがメンバー属性のセキュリティを変更することを確認してくださいlock.lockinterruptibly(); {//キューがいっぱいの場合は、notfull.await()メソッドを呼び出して、現在のスレッドがキューがいっぱいになるまで待機させます(count == items.length)notfull.await(); // enqueueメソッドを呼び出して、要素をキューエンキュー(e)に挿入します。 }最後に{lock.unlock(); }}オファーメソッドの一般的なプロセスは、オファーメソッドと同じです。ただし、キューがいっぱいになると、notfull.await()メソッドが呼び出され、現在のスレッドブロックを作成し、他のスレッドでキューが削除されるまで待ちます。キューが不満の場合、待機スレッドは目覚めます。
3.3オファー(e e、long timeout、timeunit unit)メソッド
/***キューの最後に新しい要素を追加します。キューに使用できるスペースがない場合、現在のスレッドが待機します。 *待機時間がタイムアウトを超えると、Falseが返され、追加が失敗したことを示します*/ public Booleanオファー(e、long timeout、timeunit unit)は断続的なexceptionをスローします{checknotnull(e); //最大待機の時間値を計算します。 final reentrantlock lock = this.lock; //ロックを使用して、メンバー属性のマルチスレッド変更lock.lockinterrumdibly()を確認してください。 try {//キューがいっぱいですwhile(count == items.length){// nanos <= 0は、最大待機時間が到着したことを意味するため、もう待つ必要はありません。誤ったものを返し、追加が失敗したことを示します。 if(nanos <= 0)falseを返します。 // notfull.awaitnanos(nanos)メソッドを呼び出すと、タイムアウトNANOS時間が自動的に目覚めます。 //事前に目が覚めた場合、残りの時間が返されますnanos = notfull.awaitnanos(nanos); } // enqueueメソッドを呼び出して、要素をキューエンキュー(e)に挿入します。 trueを返します。 }最後に{lock.unlock(); }}PUTメソッドの一般的なフローは、PUTメソッドと同じであり、現在のスレッドを待って待機時間を設定するために、notfull.awaitnanos(nanos)メソッドを呼び出すだけです。
4.要素メソッドを削除します
4.1削除()およびPoll()メソッド:
// AbstractQueueの親クラスのメソッドを呼び出します。 public e remove(){// Poll e x = poll()を呼び出して実装。 if(x!= null)return x;それ以外の場合は、新しいnosuchelementexception()を投げます。 } //キューの最初の要素(つまり、キューヘッダー)を削除し、返します。キューが空の場合、例外は投げかけませんが、nullを返します。 public E Poll(){final reentrantlock lock = this.lock; //ロックを使用して、メンバー属性のマルチスレッド変更lock.lock()を確認することを確認してください。 {// count == 0の場合、リストが空の場合は、nullを返します。それ以外の場合は、dequeueメソッドを呼び出してリストヘッダー要素(count == 0)を返しますか? null:dequeue(); }最後に{lock.unlock(); }}削除メソッドは、Poll()メソッドを呼び出すことにより実装されます。 Poll()メソッドでは、リストが空の場合、nullを返します。そうしないと、dequeueメソッドが呼び出され、リストヘッダー要素を返します。
4.2テイク()メソッド
/***キューの最初の要素を返して削除します。キューが空の場合、フロントスレッドが待機します。応答割り込み例の例外*/ public e take()throws arturnedexception {final reentrantlock lock = this.lock; //ロックを使用して、マルチスレッドがメンバー属性のセキュリティを変更することを確認してくださいlock.lockinterruptibly(); {//キューが空の場合は、notempty.await()メソッドを呼び出して、現在のスレッドを待たせます。 //別のスレッドが要素をキューに挿入するまで、スレッドは目覚めます。 while(count == 0)notempty.await(); // dequeueメソッドを呼び出して、リストヘッダー要素を返すDequeue()を返します。 }最後に{lock.unlock(); }}Take()メソッドが空の場合、現在のスレッドは、別のスレッドがキューに新しい要素を挿入するまで待機する必要があり、スレッドは目覚めます。
4.3世論調査(長時間、タイムナイトユニット)メソッド
/***キューの最初の要素を返して削除します。キューが空の場合、フロントスレッドが待機します。 *待機時間がタイムアウトを超えると、falseが返され、要素が失敗したことを示します*/ public E Poll(long timeout、timeUnitユニット)が中断されたexceptionをスローします{//総nanos long nanos = unit.tonanos(タイムアウト)の最大待機時間値を計算します。 final reentrantlock lock = this.lock; //ロックを使用して、メンバー属性のマルチスレッドの変更lock.lockinterrumdibly()を確認することを確認します。 try {//キューは空です(count == 0){// nanos <= 0は最大待機時間が到着したことを意味するため、もう待つ必要はありません。 if(nanos <= 0)nullを返します。 // notempty.awaitnanos(nanos)メソッドを呼び出して、スケジュールスレッドを待ってタイムアウト時間を設定します。 nanos = notempty.awaitnanos(nanos); } // dequeueメソッドを呼び出して、リストヘッダー要素を返すDequeue()を返します。 }最後に{lock.unlock(); }}Take()メソッドプロセスと同様に、現在のスレッドを待って待機時間を設定するのは、Waitnanos(Nanos)メソッドと呼ばれます。
5。要素を表示する方法
5.1 Element()およびPeek()メソッド
// AbstractQueueの親クラスのメソッドを呼び出します。 public e element(){e x = peek(); if(x!= null)return x;それ以外の場合は、新しいnosuchelementexception()を投げます。 } //キューヘッダー要素を表示public epeek(){final reentrantlock lock = this.lock; //ロックを使用して、メンバー属性のマルチスレッド変更lock.lock()を確認することを確認してください。 try {//現在のキューヘッダーreturn itemat(takeindex)の要素を返す; //キューが空のときのnull}最後に{lock.unlock(); }}vi。その他の重要な方法
6.1 EnqueueおよびDequeueメソッド
//要素xをキューのテールに挿入private void enqueue(e x){// assert lock.getholdcount()== 1; // assertアイテム[putindex] == null; //現在のputindex位置要素は、null final object [] items = this.itemsである必要があります。 items [putindex] = x; // putindexがitems.lengthに等しい場合、putindexを0にリセットしますif(++ putindex == items.length)putindex = 0; //キューの数に1つのcount ++を追加します。 //要素が挿入されているため、現在のキューは間違いなく空ではありません。その後、Notempty.signal(); } //キューヘッダーの要素を削除し、private e dequeue(){// assert lock.getholdcount()== 1; // assert items [takeindex]!= null;最終オブジェクト[] items = this.items; //現在のキューヘッダー@SuppressWarnings( "Unchecked")e x =(e)items [takeIndex]の要素を取得します。 //現在のキューヘッダー位置を項目にnullに設定します[takeindex] = null; if(++ takeIndex == items.length)takeIndex = 0; //キューの数を1カウントで引いた - ; if(itrs!= null)itrs.ElementDequeued(); //要素が削除されているため、キューは間違いなく満たされていないため、著名な条件の下で待機しているスレッドを起動します。 xを返します。 }これらの2つの方法は、要素をそれぞれキューから要素に挿入し、削除することを表し、それぞれキューから削除します。そして、彼らは待っている糸を起こしたいと思っています。要素を挿入した後、キューが空ではないようにしてはならないので、Notempty条件の下で待機しているスレッドは目覚めなければなりません。要素を削除した後、キューは不満である必要があるため、顕著な状態の下で待機するスレッドを目覚める必要があります。
6.2削除(オブジェクトO)メソッド
//キュー内のオブジェクトO要素を削除し、最大で1つのpublic boolean remove(object o){if(o == null)falseを返します。最終オブジェクト[] items = this.items; //ロックを使用して、メンバー属性のマルチスレッド変更のセキュリティを確保し、finentlantlock lock = this.lock; lock.lock(); try {//キューに値がある場合にのみ削除してください。 if(count> 0){//キューの最後の次の位置final int putindex = this.putindex; //キューヘッダーの位置int i = takeIndex; do {//現在の位置要素は、削除された要素と同じです。(o.equals(items [i])){// i position element removeat(i); // true return trueを返す; } if(++ i == items.length)i = 0; // i == putindexは、すべての要素が通過したことを意味する場合} while(i!= putindex); } falseを返します。 }最後に{lock.unlock(); }}キューから指定されたオブジェクトoを削除すると、キューをトラバースし、オブジェクトoと同じ最初の要素を削除する必要があります。キューにオブジェクトO要素がない場合は、falseを返して削除に失敗しました。
注意すべき2つのポイントは次のとおりです。
キューを通過する方法は、キューの頭からキューの終わりまで横断することです。それは、deckindexとputindexを取得する2つの変数に依存します。
Object [] items = this.itemsの理由。このコードは、同期ロックロックコードブロックに配置されていません。アイテムはメンバー変数です。スレッドが非常に多い場合、同時実行の問題はありませんか?
これは、アイテムが基本データ型ではなく参照変数であり、キューの挿入と削除操作がすべてこのアイテム配列のためにすべてであり、配列への参照が変更されていないためです。したがって、ロックコードでは、アイテムは他のスレッドによって最新の変更を取得します。ただし、int putindex = this.putindex;メソッドはコードブロックを外部にロックし、問題が発生します。
Removeat(final int removeIndex)メソッド
//キュー内の要素を削除removeIndex位置void removeat(final int removeIndex){// assert lock.getholdcount()== 1; // assert items [removeIndex]!= null; // assert removeIndex> = 0 && removeIndex <items.length;最終オブジェクト[] items = this.items; //リストヘッダーとして要素を削除する方がはるかに簡単であることを意味します。これは、dequeUnedex == takeIndex){// removeIndexの位置項目の要素を削除する場合、dequeueメソッドプロセスに似ています。 //配列の終了時に、(++ takeindex == items.length)takeIndex = 0; //キューの数を1カウントで引いた - ; if(itrs!= null)itrs.ElementDequeued(); } else {//「インテリア」final int putindex = this.putindex; for(int i = removeIndex ;;){int next = i + 1; if(next == items.length)next = 0; //キューの終わりはまだキューの終わりに到達していません。次の位置の要素は、前の位置の要素によって上書きされます(next!= putindex){items [i] = items [next]; i = next; } else {//キューnullアイテムのテール要素を設定します[i] = null; // putindex this.putindex = i;の値をリセットします。壊す; }} // count-によってキューの数を減らします。 if(itrs!= null)itrs.removedat(removeIndex); } //要素が削除されているため、キューは間違いなく満たされていないため、著名な条件の下で待機しているスレッドを起動します。 }キュー内の指定された場所の要素を削除します。削除後の配列は、2つの状況に分割されるキューフォームを維持できることに注意してください。
上記はこの記事のすべての内容です。みんなの学習に役立つことを願っています。誰もがwulin.comをもっとサポートすることを願っています。