ぱそちゃんです
つぎは仮想記憶方式の問題です
**********************************************
H29年度 春期基本情報技術者試験 午前問題 問19
仮想記憶方式のコンピュータにおいて、実記憶に割り当てられるページ数は3とし、
追い出すページを選ぶアルゴリズムは、FIFOとLRUの二つを考える。
あるタスクのページのアクセス順序が
1,3,2,1,4,5,2,3,4,5
のとき、ページを置き換える回数の組み合わせとして、適切なものはどれか。
****************************************
解説
ページングの問題ですね
FIFOはファーストインファーストアウト
最初に入れたやつを最初に出す
LRUはリーストリーセントリーユーズド
使われてから一番時間がたったやつから出す
というわけで 記憶できる3ページ分を
まず 132
1は記憶してるからOK
次の4で両方とも1回目のページ追い出しですね
FIFOだったら 最初に入れたやつだから 1を消して 324
LRUだったら 一番古い参照だから 3を消して 214
次の5で2回目のページ追い出し
FIFOは 3を消して 245
LRUは 2を消して 145
次の2はFIFOの場合は残っているのでページ追い出しはなし
LRUだけ3回目のページ追い出し 1を消して 452
次の3は両方ないのでページ追い出し
FIFOは3回目 2を消して 453
LRUは4回目 4を消して 523
次の4はFIFOはあるのでページ追い出しはなし
LRUだけ5回目 5を消して 234
最後の5もFIFOはあります。
LRUはないので6回目のページ追い出し
2を消して 345
ということでFIFOが3回 LRUが6回の
選択肢イが正解です
3ページだったから簡単でしたね
����29�N �t�� ��{���Z�p�� �ߑO ��19
��19�@�@ ���z�L�������@���z�L�������̃R���s���[�^�ɂ����āC���L���Ɋ��蓖�Ă���y�[�W���͂R�Ƃ��C �ǂ��o���y�[�W��I�ԃA���S���Y���́CFIFO �� LRU �̓���l����B ����^�X�N�̃y�[�W�A�N�Z�X������
�@�@�@1, 3, 2, 1, 4, 5, 2, 3, 4, 5
�@�̂Ƃ��C�y�[�W��u��������̑g�����Ƃ��ēK�Ȃ��̂͂ǂꂩ�B
�@�@ | �@�@FIFO | �@�@LRU |
�@ �A�@ | �@�@�@3�@ | �@�@�@2�@ |
�@ �C�@ | �@�@�@3�@ | �@�@�@6�@ |
�@ �E�@ | �@�@�@4�@ | �@�@�@3�@ |
�@ �G�@ | �@�@�@5�@ | �@�@�@4�@ |
�@FIFO�iFirst-in First-out�j�́A�ŏ��ɓ������y�[�W���ŏ��ɒu������������ł���B
�@LRU�iLeast Recently Used�j�Ō�ɎQ�Ƃ���Ă���A�ł����Ԃ��o�߂��Ă���y�[�W��u������������ł���B
�@�}�̐Ԏ��̕������u���������y�[�W�ł���B
��Q�P
���z�L�������̃R���s���[�^�ɂ����āA���L���Ɋ��蓖�Ă���y�[�W����3�Ƃ��A�ǂ��o���y�[�W��I�ԃA���S���Y���́AFIFO��LRU�̓���l����B����^�X�N�̃y�[�W�̃A�N�Z�X������ 1, 3, 2, 1, 4, 5, 2, 3, 4, 5 �̂Ƃ��A�y�[�W��u��������̑g�ݍ��킹�Ƃ��ēK�Ȃ��̂͂ǂꂩ�B
�@�@�@����������������������
�@�@�@���e�h�e�n�� �k�q�t ��
�@��������������������������
�@���A�� �@�R�@ �� �@�Q�@ ��
�@��������������������������
�@���C�� �@�R�@ �� �@�U�@
��
�@��������������������������
�@���E�� �@�S�@ �� �@�R�@ ��
�@��������������������������
�@���G�� �@�T�@ �� �@�S�@ ��
�@��������������������������
����
�C
���
FIFO (First In, First Out) �́A������o���ɂ��u������A���S���Y���ł���B
LRU (Least Recently Used) �́A�Q�Ƃ���Ă��Ȃ����Ԃ��ł������y�[�W��u���ΏۂƂ���A���S���Y���ł���B
�y�[�W����3�ł��邽�߁A���蓖�Ă���y�[�W�̏�Ԃ͈ȉ��̂悤�ɂȂ�B
�yFIFO�̏ꍇ�z
���͒u������
1: 1
3: 1, 3
2: 1, 3, 2
1: 1, 3, 2
4: 3, 2, 4
5: 2, 4, 5
2: 2, 4, 5
3: 4, 5, 3
4: 4, 5, 3
5: 4, 5, 3
����āA3���u�������B
�yLRU�̏ꍇ�z
�Ԏ��͎��̒u���Ώۃy�[�W
���͒u������
1: 1
3: 1, 3
2: 1, 3, 2
1: 1, 3, 2
4: 1, 4, 2
5: 1, 4, 5
2: 2, 4, 5
3: 2,
3, 5
4: 2, 3, 4
5: 5, 3, 4
����āA
6���u�������B
���z�L�������̃R���s���[�^�ɂ����āA���L���Ɋ��蓖�Ă���y�[�W����3�Ƃ��A�ǂ��o���y�[�W��I�ԃA���S���Y���́AFIFO��LRU�̓���l����B
����^�X�N�̃y�[�W�̃A�N�Z�X������
�@1, 3, 2, 1, 4, 5, 2, 3, 4, 5
�̂Ƃ��A�y�[�W��u��������̑g�ݍ��킹�Ƃ��ēK�Ȃ��̂͂ǂꂩ�B
FIFO | LRU | |
�A | 3 | 2 |
�C | 3 | 6 |
�E | 4 | 3 |
�G | 5 | 4 |
�����@�C
�y����z
FIFO�ALRU�̎��̂��ꂼ��̃y�[�W�̒u�������𐔂���B
- FIFO
�ŏ��̃y�[�W�̏�Ԃ͉��������Ă��Ȃ��̂Ńy�[�W�̏�Ԃ͋�ł���B
�������ŁA�E���獶�Ƀy�[�W�Ɋ��蓖�Ă�ꂽ���Ƃ���B(��ԍ����Ō�Ɋ��蓖�Ă�ꂽ�y�[�W)- �y�[�W1�ɃA�N�Z�X����B
- �y�[�W3�ɃA�N�Z�X����B
- �y�[�W2�ɃA�N�Z�X����B
- �y�[�W1�ɃA�N�Z�X����B
�y�[�W1�͂��łɎ��L���Ɋ��蓖�Ă��Ă���̂Ńy�[�W�̏�Ԃ͕ς��Ȃ��B - �y�[�W4�ɃA�N�Z�X����B
�ŏ��Ɋ��蓖�Ă�ꂽ�p�[�W1���ǂ��o����y�[�W4�����蓖�Ă���B - �y�[�W5�ɃA�N�Z�X����B
�ŏ��Ɋ��蓖�Ă�ꂽ�p�[�W3���ǂ��o����y�[�W5�����蓖�Ă���B - �y�[�W2�ɃA�N�Z�X����B
�y�[�W2�͂��łɎ��L���Ɋ��蓖�Ă��Ă���̂Ńy�[�W�̏�Ԃ͕ς��Ȃ��B - �y�[�W3�ɃA�N�Z�X����B
�ŏ��Ɋ��蓖�Ă�ꂽ�p�[�W2���ǂ��o����y�[�W3�����蓖�Ă���B - �y�[�W4�ɃA�N�Z�X����B
�y�[�W4�͂��łɎ��L���Ɋ��蓖�Ă��Ă���̂Ńy�[�W�̏�Ԃ͕ς��Ȃ��B - �y�[�W5�ɃA�N�Z�X����B
�y�[�W5�͂��łɎ��L���Ɋ��蓖�Ă��Ă���̂Ńy�[�W�̏�Ԃ͕ς��Ȃ��B
- LRU
�ŏ��̃y�[�W�̏�Ԃ͉��������Ă��Ȃ��̂Ńy�[�W�̏�Ԃ͋�ł���B
�������ŁA�E���獶�ɍŋ߃A�N�Z�X�������Ƃ���B(��ԍ����Ō�ɃA�N�Z�X�����y�[�W)- �y�[�W1�ɃA�N�Z�X����B
- �y�[�W3�ɃA�N�Z�X����B
- �y�[�W2�ɃA�N�Z�X����B
- �y�[�W1�ɃA�N�Z�X����B
�y�[�W1�͂��łɎ��L���Ɋ��蓖�Ă��Ă���̂ŁA�y�[�W�̒u�������͔������Ȃ����A�������ς��B - �y�[�W4�ɃA�N�Z�X����B
�����Ƃ��A�N�Z�X�̂Ȃ��y�[�W3���ǂ��o����y�[�W4�����蓖�Ă���B - �y�[�W5�ɃA�N�Z�X����B
�����Ƃ��A�N�Z�X�̂Ȃ��y�[�W2���ǂ��o����y�[�W4�����蓖�Ă���B - �y�[�W2�ɃA�N�Z�X����B
�����Ƃ��A�N�Z�X�̂Ȃ��y�[�W1���ǂ��o����y�[�W2�����蓖�Ă���B - �y�[�W3�ɃA�N�Z�X����B
�����Ƃ��A�N�Z�X�̂Ȃ��y�[�W4���ǂ��o����y�[�W3�����蓖�Ă���B - �y�[�W4�ɃA�N�Z�X����B
�����Ƃ��A�N�Z�X�̂Ȃ��y�[�W5���ǂ��o����y�[�W4�����蓖�Ă���B - �y�[�W5�ɃA�N�Z�X����B
�����Ƃ��A�N�Z�X�̂Ȃ��y�[�W2���ǂ��o����y�[�W5�����蓖�Ă���B
�y�L�[���[�h�z
�E�y�[�W�u�����A���S���Y��
- �y�[�W�u�����A���S���Y��
�y�[�W���O�ɂ�鉼�z�L�������Ńy�[�W�t�H�[���g�ɔ����y�[�W�A�E�g(��L������f�[�^�����C�f�B�X�N�Ȃǂɑޔ����鑀��)����y�[�W�����߂���@�ɂ͊������A��\�I�Ȃ��̂Ƃ��ẮA- LRU(Least Recently Used)
�ł��������ԃA�N�Z�X���Ȃ��y�[�W���y�[�W�A�E�g����B - FIFO(First-In First-Out)
�ł��������ԃy�[�W�C����Ԃɂ���y�[�W���y�[�W�A�E�g����B - NFU(Not Frequently Used)
�A�N�Z�X�̏��Ȃ��y�[�W���y�[�W�A�E�g����B - NRU(Not Recently Used)
��莞�ԃA�N�Z�X�̂Ȃ��y�[�W���y�[�W�A�E�g����B
- LRU(Least Recently Used)
�����ƁA�u�y�[�W�u�����A���S���Y���v�ɂ��Ē��ׂĂ݂悤�B