はじめに
Belady's anomaly とは 「割り当て主記憶容量を増やしたとき、ページフォールト回数が多くなる」 ことをいいます。
直観的には、割り当て主記憶容量を増やせば、ページフォールト回数は少なくなりそうです。ただ、特定の場合には belady's anomaly が発生するようです。
この記事ではFIFOの場合を例に Belady's anomaly の気持ちを見ていきます。
Belady's anomaly の気持ち
belady's anomaly の具体例として、枠数を $ 小=5, 大=6 $、参照列を、1,2,3,4,5,6,1,2,7,3,4,5, 1,2,3,4,5,6,7, 1,2,3,4,5,6,7, … (以下1,2,3,4,5,6,7 の繰り返し) とすると、繰り返しごとに枠数大の方がページフォールト回数が多くなります。 参照列は、準備部分である1,2,3,4,5,6,1,2,7,3,4,5と繰り返し部分である1,2,3,4,5,6,7に分解することができます。準備部分でページ枠の順番を調整するのが鍵になります。 以下、実際に振る舞いを見ていきましょう。
準備部分
| step | ref | 小ﾍﾟｰｼﾞ枠 | 小ﾌｫｰﾙﾄ | 小計 | 大ﾍﾟｰｼﾞ枠 | 大ﾌｫｰﾙﾄ | 大計 |
|---|---|---|---|---|---|---|---|
| 1 | 1 | [1] | True | 1 | [1] | True | 1 |
| 2 | 2 | [1, 2] | True | 2 | [1, 2] | True | 2 |
| 3 | 3 | [1, 2, 3] | True | 3 | [1, 2, 3] | True | 3 |
| 4 | 4 | [1, 2, 3, 4] | True | 4 | [1, 2, 3, 4] | True | 4 |
| 5 | 5 | [1, 2, 3, 4, 5] | True | 5 | [1, 2, 3, 4, 5] | True | 5 |
| 6 | 6 | [2, 3, 4, 5, 6] | True | 6 | [1, 2, 3, 4, 5, 6] | True | 6 |
| 7 | 1 | [3, 4, 5, 6, 1] | True | 7 | [1, 2, 3, 4, 5, 6] | False | 6 |
| 8 | 2 | [4, 5, 6, 1, 2] | True | 8 | [1, 2, 3, 4, 5, 6] | False | 6 |
| 9 | 7 | [5, 6, 1, 2, 7] | True | 9 | [2, 3, 4, 5, 6, 7] | True | 7 |
| 10 | 3 | [6, 1, 2, 7, 3] | True | 10 | [2, 3, 4, 5, 6, 7] | False | 7 |
| 11 | 4 | [1, 2, 7, 3, 4] | True | 11 | [2, 3, 4, 5, 6, 7] | False | 7 |
| 12 | 5 | [2, 7, 3, 4, 5] | True | 12 | [2, 3, 4, 5, 6, 7] | False | 7 |
準備部分では小の方がフォールト回数が多いです。小と大で順番が変わっていることが重要です。大は1,2,3,4,5,6,7の順が保たれているので、これからのループは最も不利(必ずフォールト)になります。
1ループ目
| step | ref | 小ﾍﾟｰｼﾞ枠 | 小ﾌｫｰﾙﾄ | 小計 | 大ﾍﾟｰｼﾞ枠 | 大ﾌｫｰﾙﾄ | 大計 |
|---|---|---|---|---|---|---|---|
| 13 | 1 | [7, 3, 4, 5, 1] | True | 1 | [3, 4, 5, 6, 7, 1] | True | 1 |
| 14 | 2 | [3, 4, 5, 1, 2] | True | 2 | [4, 5, 6, 7, 1, 2] | True | 2 |
| 15 | 3 | [3, 4, 5, 1, 2] | False | 2 | [5, 6, 7, 1, 2, 3] | True | 3 |
| 16 | 4 | [3, 4, 5, 1, 2] | False | 2 | [6, 7, 1, 2, 3, 4] | True | 4 |
| 17 | 5 | [3, 4, 5, 1, 2] | False | 2 | [7, 1, 2, 3, 4, 5] | True | 5 |
| 18 | 6 | [4, 5, 1, 2, 6] | True | 3 | [1, 2, 3, 4, 5, 6] | True | 6 |
| 19 | 7 | [5, 1, 2, 6, 7] | True | 4 | [2, 3, 4, 5, 6, 7] | True | 7 |
大は毎回フォールトします。小は順がくずれている分、フォールトをしなくてよいタイミングがあり、そのおかげで順の崩れも保たれます。
2ループ目
| step | ref | 小ﾍﾟｰｼﾞ枠 | 小ﾌｫｰﾙﾄ | 小計 | 大ﾍﾟｰｼﾞ枠 | 大ﾌｫｰﾙﾄ | 大計 |
|---|---|---|---|---|---|---|---|
| 20 | 1 | [5, 1, 2, 6, 7] | False | 0 | [3, 4, 5, 6, 7, 1] | True | 1 |
| 21 | 2 | [5, 1, 2, 6, 7] | False | 0 | [4, 5, 6, 7, 1, 2] | True | 2 |
| 22 | 3 | [1, 2, 6, 7, 3] | True | 1 | [5, 6, 7, 1, 2, 3] | True | 3 |
| 23 | 4 | [2, 6, 7, 3, 4] | True | 2 | [6, 7, 1, 2, 3, 4] | True | 4 |
| 24 | 5 | [6, 7, 3, 4, 5] | True | 3 | [7, 1, 2, 3, 4, 5] | True | 5 |
| 25 | 6 | [6, 7, 3, 4, 5] | False | 3 | [1, 2, 3, 4, 5, 6] | True | 6 |
| 26 | 7 | [6, 7, 3, 4, 5] | False | 3 | [2, 3, 4, 5, 6, 7] | True | 7 |
大は1ループ目と同様です。小は1ループ目とページ枠の内容は異なりますが、同様に順の崩れが保たれています。
3ループ目
| step | ref | 小ﾍﾟｰｼﾞ枠 | 小ﾌｫｰﾙﾄ | 小計 | 大ﾍﾟｰｼﾞ枠 | 大ﾌｫｰﾙﾄ | 大計 |
|---|---|---|---|---|---|---|---|
| 27 | 1 | [7, 3, 4, 5, 1] | True | 1 | [3, 4, 5, 6, 7, 1] | True | 1 |
| 28 | 2 | [3, 4, 5, 1, 2] | True | 2 | [4, 5, 6, 7, 1, 2] | True | 2 |
| 29 | 3 | [3, 4, 5, 1, 2] | False | 2 | [5, 6, 7, 1, 2, 3] | True | 3 |
| 30 | 4 | [3, 4, 5, 1, 2] | False | 2 | [6, 7, 1, 2, 3, 4] | True | 4 |
| 31 | 5 | [3, 4, 5, 1, 2] | False | 2 | [7, 1, 2, 3, 4, 5] | True | 5 |
| 32 | 6 | [4, 5, 1, 2, 6] | True | 3 | [1, 2, 3, 4, 5, 6] | True | 6 |
| 33 | 7 | [5, 1, 2, 6, 7] | True | 4 | [2, 3, 4, 5, 6, 7] | True | 7 |
3ループ目は1ループ目と同じになっています。
よって、以下ループを繰り返すと常に大の方が多くフォールトします。
おわりに
「割り当て主記憶容量を増やしたとき、ページフォールト回数が多くなる」は直観に反することであり、最初は驚きましたが、具体例を見ることで、なるほどなと思いました。