linux - スレッドセーフな検索と追加

Question

次のことができる必要があります。

1. リンクされたリストを検索します。
2. 見つからない場合に備えて、新しいノードをリストに追加します。
3. ほとんどがリストで読み取られるため、スレッドセーフで rwlock を使用してください。

私が抱えている問題は、read_lock から write_lock に昇格するときに、read_lock を保持しているリスト検索を行っているときに、他のスレッドが write_lock を待っていないことを確認するために、リストを再度検索する必要があることです。

二重リスト検索 (おそらくある種の seq_lock) を行わずに上記を達成する別の方法はありますか?

Answer 1

リンク リストをソート済みリンク リストに変換します。新しいノードを追加するときは、リスト全体を検索するのではなく、2 つのノードのみを検査してロックを取得している間に、別のライターが同等のノードを追加したかどうかを再度確認できます。新しいノードのソート順を決定する必要があるため、各ノードの挿入に少し時間がかかりますが、リスト全体を検索する必要がないため、時間を節約できます。全体として、おそらく多くの時間を節約できます。