0

私は条件変数の読み取りの分担を行いましたが、それらの使用方法を理解できずに立ち往生しています。

私はツリーを持っています。現在、すでに存在するノードを挿入すると、0 が返されます。これは、既に存在しているため失敗したことを意味します。

私は現在、pthreads サポートを拡張したいと考えています。既に存在して 0 を返すので実行できないと言うのではなく、待機キューに置き、要求されたノードが削除されたら、先に進んで挿入します。

例えば、

ツリーに値が 1、5、10 の 3 つのノードがあるとします。値が 10 の新しいノードを挿入したい場合は、0 を返して値が既に存在するというエラーをスローするのではなく、値が 10 のノードを待つ必要があります。削除するには、削除したら、戻って挿入する必要があります。

私の挿入関数elseブロックは、ノードがその値で存在することを以前に検査した後、0を返します。それが存在することを知るロジックが正常に機能することを確信できます。今は、待機する場所に条件付き変数サポートを追加しようとしています. datafield 条件は挿入の最初の行で初期化されるため、それも同様に行われます。このブロックに入ると、cond_wait が実行される唯一のコード行になり、delete が合図するまで単に待機することを期待しています。ここでの私のアプローチは正しいですか？削除されている場合、どのように通知すればよいですか? ここで私を助けてください、私はこれを理解しようとする例を読んだり見たりするのに何時間も費やしました.

コード、

  else

      {
        //IF DUPLICATE EXISTS
        pthread_mutex_lock(&m);
        node->counter++;
        pthread_cond_wait(&node->condition, &m);
        _insert(string, strlen, ip4_address, node, NULL, NULL);
        pthread_mutex_unlock(&m);

        return 1;//I CHANGED IT FROM 0 to one, since if signalled, and if reached to this limit
        //it was probably successful

    }
4

2 に答える 2

1

条件変数の待機は、ループでラップする必要があります。ループのガードは、ミューテックスによって保護された共有データの状態をテストします。条件変数をそのまま使用しても意味がありません。

値が 10 のノードが削除されるのを待ってから挿入するのが理にかなっている場合は、次のようなロジックで実行されます。

lock(mutex)
while (tree.contains(key))
  wait(cond, mutex)
tree.insert(key, value)
unlock(mutex)

他のタスクはこれを行います:

lock(mutex)
tree.delete(key)
unlock(mutex)
broadcast(cond) // could be in the mutex, but better outside!

CAR Hoare がモニターと条件変数を発明したとき、元の概念は少し異なっていました。複数のプロセッサでの効率に関する懸念は問題ではなかったため、次のロジックがサポートされていました。

enter(monitor);
if (tree.contains(key))   // no loop
  wait(cond, monitor)
tree.insert(key, value)
leave(monitor);

他のタスクが条件を通知すると、他のタスクがモニターを占有することなく、待機中のタスクがアトミックにモニターに戻されることが保証されていました。したがって、たとえば、タスクがモニターにあり、ノード 10 を削除し、条件変数を通知する場合、その条件変数を待機している最初のタスクは、すぐにモニターを取得することが保証されます。POSIXミューテックスと条件ではそうではありません（正当な理由により）。

ミューテックスとモニターのもう 1 つの違いは、条件変数を通知するためにスレッドがミューテックスを保持する必要がないことです。実際、そうしないのは良い考えです。条件変数のシグナル送信は、コストのかかる操作になる可能性があります (カーネルへのトリップ)。ミューテックスは、競合を最小限に抑えるために、できるだけ短い (理想的にはほんの数命令) 重要な領域を保護する必要があります。

さらに別の違いは、POSIX 条件には、pthread_cond_broadcast条件で待機しているすべてのスレッドをウェイクアップする関数があることです。これは常に、デフォルトで使用する正しい関数です。単一のスレッドをウェイクアップすることが正しいことが明らかな (またはそれを示すことができる) 状況では、関数pthread_cond_signalを使用してコードを最適化できます。

于 2013-04-12T22:40:35.017 に答える
1

仮定は次のとおりです。

struct tree
{
   ... // some other data (whatever)
   pthread_mutex_t mitex;
   pthread_cond_t  cond;
};

ヘルパー関数:

int tree_contains_value(struct tree *t, int value)
{
    return ...; // returns 0 or 1
}

そして、ここに挿入があります：

void tree_insert(struct tree *t, int val)
{
    pthread_mutex_lock(&t->mutex);
    while (tree_contains_value(t, value))
    {
        pthread_cond_wait(&t->cond, &t->mutex);
    }
    ... // do actual insert
    pthread_mutex_unlock(&t->mutex);
}

そして除去：

void tree_remove(struct tree *t, int val)
{
    pthread_mutex_lock(&t->mutex);
    ... //remove value
    pthread_cond_broadcast(&t->cond); // notify all wating threads if any
    pthread_mutex_unlock(&t->mutex);
}
于 2013-04-12T22:51:50.833 に答える