バッファがあふれないサイズの条件式を、たまる量から考える
基本情報技術者試験 平成29年度春期 午前 問17 ／ ソフトウェア › オペレーティングシステム
過去問にチャレンジ
図の送信タスクから受信タスクにT秒間連続してデータを送信する。1秒当たりの送信量をS，1秒当たりの受信量をRとしたとき，バッファがオーバーフローしないバッファサイズLを表す関係式として適切なものはどれか。ここで，受信タスクよりも送信タスクの方が転送速度は速く，次の転送開始までの時間間隔は十分にあるものとする。
- ア
L＜(R－S)×T
- イ
L＜(S－R)×T
- ウ
L≧(R－S)×T
- エ
L≧(S－R)×T
会話形式の解説
講師この問題では、送信タスクと受信タスクの間にあるバッファに、データがどれだけたまるかを考えます。見るところは二つです。引き算をどちらからするかと、不等号の向きです。
受験者図では、送信タスクからバッファへSが入って、バッファから受信タスクへRが出ていきますね。選択肢はR－SとS－Rの式、それに＜と≧の向きを組み合わせたものなので、全部同じように見えてしまいます。
講師では、まず引き算から決めましょう。問題文には、受信タスクより送信タスクの方が速いとあります。SとRはどちらが大きいでしょうか。
受験者送信の方が速いので、S＞Rです。入る量の方が多いので、毎秒S－Rずつバッファにたまっていく、ということでしょうか。
講師そのとおりです。ここで、R－Sを使った二つの式を見てください。S＞Rなら、R－Sに正の時間Tをかけた値はどうなりますか。
受験者マイナスになります。そうすると、Lがその値より小さいという式は、マイナスより小さいバッファサイズという意味になってしまいますね。
講師はい。そんなバッファサイズはありえないので、その式は使えません。反対に、Lがその値以上という式は、どんなに小さいLでも成り立ってしまいます。実際には毎秒S－Rずつたまるので、その式を満たしてもあふれないとは言えません。
受験者では、S－Rの二つのどちらかですね。たまる量が一番多くなるのはいつですか。
講師送信が続いているT秒間は、たまる量が増え続けます。なので、送信が終わった時点が最大で、(S－R)×Tです。バッファがあふれないためには、Lとこの最大量はどういう関係であればよいでしょうか。
受験者最大量が入りきればよいので、Lは(S－R)×T以上ですね。Lが(S－R)×Tより小さい式だと、送信の途中で容量が足りなくなってあふれてしまいます。
講師正解です。答えはL≧(S－R)×Tです。数字で確かめておきましょう。送信が毎秒100、受信が毎秒80なら、毎秒20ずつたまります。10秒続けると200なので、Lは200以上必要です。
受験者数字にすると分かりやすいです。「次の転送開始までの時間間隔は十分にある」という条件には、どういう意味があるのですか。
講師次の送信が始まるまでに、バッファは空になると考えてよい、という意味です。前回の残りを足さなくてよいので、1回分の送信だけを考えればよいわけです。まとめると、たまる量は入る速度から出る速度を引いて求めます。あふれない条件は「容量≧最大蓄積量」です。この二つを押さえておけば、同じような問題にも対応できます。
まとめ
送信側が受信側より速い（S＞R）とき、バッファには毎秒S－Rずつデータがたまります。たまる量はT秒間の送信のあいだ増え続けるので、送信が終わった時点の(S－R)×Tが最大です。あふれないためには、容量Lがこの最大量以上であればよいので、条件はL≧(S－R)×Tになります。S＞Rなので、R－Sを含む式は右辺が負になり、条件として意味をなしません。L＜(S－R)×Tでは、送信の途中でバッファがあふれてしまいます。
解答・解説
正解はエです
この問題のテーマ
送信側が受信側より速いとき、バッファに一時的にたまるデータ量を見積もり、あふれないために必要なバッファサイズの条件を式で表せるかを問う問題です。
解き方の考え方
図では、送信タスクからバッファへ毎秒Sが入り、バッファから受信タスクへ毎秒Rが出ていきます。問題文から送信の方が速いのでS＞Rです。入る量が出る量を上回るため、差の分が毎秒バッファにたまります。たまる量は送信を続けるT秒間増え続け、送信が終わった時点で最大の(S－R)×Tになります。この最大量を収められる大きさ、つまりこの値以上のLがあればあふれません。
選択肢ごとの解説
- ×ア L＜(R－S)×TアのL＜(R－S)×Tでは、S＞Rなので右辺は負の値になります。負の値より小さいバッファサイズはありえず、実際にたまる量とも合わないため、あふれない条件を表していません。
- ×イ L＜(S－R)×TイのL＜(S－R)×Tは、たまる量の計算は正しいものの、Lがその最大蓄積量より小さいという条件になっています。これでは送信の途中で容量が足りなくなり、バッファがあふれてしまいます。
- ×ウ L≧(R－S)×TウのL≧(R－S)×Tは右辺が負なので、どんなに小さいLでも成り立ってしまいます。実際には毎秒S－Rずつたまっていくので、この式を満たしてもあふれないとは言えません。
- ○エ L≧(S－R)×TエのL≧(S－R)×Tは、T秒間の送信が終わった時点の最大蓄積量以上の容量を求める条件です。最大量が入るなら送信中のどの時点でもあふれないので、この式が適切です。
補足
たとえば送信が毎秒100、受信が毎秒80なら、バッファには毎秒20ずつたまります。10秒間送り続けると20×10＝200たまるので、Lは200以上必要です。「次の転送開始までの時間間隔は十分にある」という条件は、次の送信が始まるまでにバッファが空になると考えてよい、という意味です。
POINT
- バッファの蓄積量は「入る速度－出る速度」の分だけ毎秒変わります。
- 入る量の方が多い状態が続くと蓄積量は増え続けるので、送信が終わる時点の量が最大になります。
- あふれない条件は「容量≧最大蓄積量」なので、不等号は≧の向きになります。
- S＞Rという前提から、R－Sを含む式は負になり、容量の条件として意味をなさないと判断できます。