1つの物理タイマーを持つ複数の仮想タイマーをシミュレートする

Question

ネットワーキング割り当てでCを使用して選択リピートプロトコルを実装しようとしていますが、個々のパケットごとにタイマーをシミュレートする方法がわかりません。私は1つのタイマーにしかアクセスできず、以下で説明するように関数を呼び出すことができます。

/* start timer at A or B (int), increment in time*/ 
extern void starttimer(int, double);  

/* stop timer at A or B (int) */ 
extern void stoptimer(int);    

黒瀬とロスは、単一のハードウェアタイマは、複数の論理タイマー[Varghese 1997]の 動作を模倣するために使用することができる

こと彼らのネットワークの教科書に記載されました。

そして、私はあなたが単一の物理タイマーを使用して複数の仮想タイマーをシミュレートすることができます同様のassignment

ために、以下のヒントを見つけました。基本的な考え方は、仮想タイマーの連鎖を有効期限内に整理し、最初の仮想タイマーの満了時に物理タイマーがオフになることです。

しかし、エミュレータが別の抽象レイヤにあるため、RTT以外の時間変数にアクセスすることはできません。この場合、個々のパケットのタイマーはどのように実装できますか？

Answer 1

これは、カーネルレベルで実装されているのと同じ方法で実行できます。各タイマーが前のタイマーとの相対的なタイムアウトを持つ「タイマー」のリンクリストを持つ必要があります。それは次のようなものになります。 タイマ1：t0から500ms、タイマ2：t0から400ms、タイマ3 t0から1000ms。

その後、各要素は、このような以前のもの、に対するタイムアウトを持っているリンクリストがあります：

頭部>タイマ2（400msの） - >タイマ1（100ミリ秒） - >タイマ3（500ミリ秒）を

すべての要素には、timerID、相対タイムアウト、絶対初期化時間（エポックからのタイムスタンプ）の最小値が含まれます。タイマーごとにコールバックポインターを追加できます。

あなたはあなたの唯一のタイマーを使用すると、リストの最初の要素の相対的なタイムアウトにタイムアウトを設定します。あなたは理想的には、タイマ2に関連したコールバックを実行し、おそらく、最初の要素を削除しますタイムアウトの後400msの（タイマ2）

このコールバックは別のワーカースレッドで実行されます。その後、次の要素Timer1：100msの相対タイムアウトで新しいタイムアウトを設定します。

ここで、t0から300 ms後に新しいタイマーを作成する必要がある場合は、タイマーのリンクリストをナビゲートする適切な位置に挿入する必要があります。 Timer4の相対タイムアウトは2,300になります。これは（Timer2.RelativeTimeout - （now - Timer2.AbsoluteTimeout））で計算され、対応する位置を見つけるためにリンクされたリストを調べ、各前の要素の相対タイムアウトを加えます。あなたのリンクリストにはなります：

頭部>タイマ2（400msの） - >タイマ1（100ミリ秒） - >タイマ3（500ミリ秒） - >タイマー4（2300）

あなたは物理的なものと多くの論理のタイマーを実装する。このように

タイマー。タイマーを作成して検索する時間はO（n）になりますが、挿入パフォーマンスにさまざまな改善を加えることができます。最も重要なのは、タイマーのタイムアウト処理と更新がO（1）であることです。削除の複雑さは、タイマーを見つけるためのO（n）と削除のためのO（1）になります。

タイマーを制御するスレッドとタイマーを挿入または削除するスレッドの間で競合が発生する可能性があります。このタイマーをユーザー空間に実装する1つの方法は、条件変数と待機タイムアウトです。