����� ������
|
..� ��� �� ������������ ������ �������,-
�����, �� ����������� �������� ���� � ������
�. ������� |
�����������, ��� ���� ����� ���������������� ������� �������� �������"
� ����� ������������ ������ � �������� � �� ������ ����� �����-�� �����
������������� ��������, �� �������� ������������, ����� ������ ���������
����� �������������.
���� �������� ������ �������� � ��� ������ ������ ��������, � ������ �������
�� ������ �������� � �������� "������" (victim) ��� ��������
��� ������, ������� �� ��� ������� �� ����� ����� � ������� ������. �������������,
�� ������ ������� � ���������� ���� ������� (���� � ��� ���� �� �����
�� ��������), ��� ����� ����������!
��� ������� �������� ������ �������� � ������ ��������: ����� �������
(��� ������ ������, ������� �� ����������� ��������� �� ����� ����������
� ������� ������, �������� ����� �������� � ����������� �����. ��� ����������������
�� ������ ����� �������� ������ ������ ���� ����������� ������� � ���������
������, � ������ ����� ����� ����� ���������� ���������� ��������.) ��,
��� ������ ����� �� ����� �������������� � �������. �������, ����� �������������
� ������� ����� �������� ��������, ��� ����� ���������� ����������. ��
������ ������������� � ���, ��� ����� ��������������, ������ �� ���������
����������� ���������� ��������� � ���������. ����� ������������� �� ������
��������� ���������, ������� ����� ��������� �������������� ���������
� ��������� ����������� ��� ���������� ���� ����������.
����� ������� ��������� � ����������� �������� ��������� ������. ��� ����
�� ���� �������� ������� ���������� � ������� ������������� � �. �., �����
���� ���������� ������������� ������������� ������������ ���������������
�����. ��������, ��� ��� ���� ��������� ������ ���������� �������������
����� ��������
����� ����� ������� ��, ��� ������ ����� ��������� � ������. ��� ����������
���������� FIFO (First In, First Out, ������
�����, ������ �����). �����, ��� ��� ��� ���� ������� ���������� ��������
� ����� ����������, ����� �� ��� ���������.
����� ������ � VAX/VMS � Windows NT/2000/XP
� VAX/VMS � Windows NT/2000/XP ����������� ���������� ������� ����� ���������.
� ���� �������� ��������, ����������� �������, ����������� �� ���������
������������ ������ (� ���������������� ����������� ������������ ��� ����������),
�� �� �������� ���������� ��� ������ �����. ������ ����� ��������, ����������
��� �������������, ���������� � ��� ��������� �������, �������, �� ����������������,
������������ � ��� ��������� ���� � ����� �������� ����� �������� �����������
������. � VAX/VMS ���� ��� ������� �� ���� �������� (���. 5.19).
1. ������� ���������������� �������, ������ ������ ��
���� (�� ���� ������, ��� �������� ��������� �� ������ �������).
2. ������� ������������������ �������.
3. ������� ��������� ������� (������������� ���������� ���������� ���
�������������� ����� �� ����������).
������� � ������ ������������ ����� ���� ��������� ��� ����������������,
��� � ������������������ ��������, ������ ��� �������� ���������� ��������
� ������� ��������� ���� ������������ ������ �������� �� ������ � �������
��������.

���. 5.19. ����������� ������ VAX/VMS
����������� ���������� �����, ������� �� ���������� � �����
�� ���������� ��������� ��������, � ������� �������� ����� �� � �����
�� �������� ����. ���� �������� ���, �� ��� ���������� �������� ��������
� �������� ������������ ������ (���. 5.20).
����� �������� ��������� ����� ������ ���������� �������, �� ������������
������� �������� ��������� � �����. � VAX/VMS ��� ��������� ����������
� ����������� ������� ���� �������: � ������� ������������ ���� �����
�� ����� �������� ��������� ���������� �� ��������. ��� ���������� �����
�� � ������������ ����� ������ ����� �������� ����������� ����� �����
������������. ��� �������� ���������� ����� ������� ������� ������������
������ ������� ���������� ���� ��� ��������� ������� ����������� ������.
Windows NT (� ����� ������� ������ ���� �������, 2000/��) �������� ���������
����� ��������� ������� �����������, �� ������������ �������������� �������
������� ��� ������ ���������. ������� �� �������� ��� ��� ���������� �����
������������� ������ ��� ������� ��������� ������ �������� ������������������.
��-��������, ��� ������� ����������� ��������� ������������� � ������������
��������� ���� ��������� �������.
���, ������ ��������� �������� � ����������������� ��������� Windows 2000
Wokrstation � 256 ����� ���, ����� ���� ������ �� ������ ��� ��������������
� far ���� ������� 64 �����. ���� �� ����������� 1/4 ��������� �����������
������. ��� �� �����, ������ "����� � ����", �� �������� ����
�� <Ctrl>+<Alt>+<Del>, � ���������� � ���� ���������
���������� ����� ��� ����,����� ������� ������ ��� ��������� ���������
��������������� �, � ����� ������, ������, ��� ����� ������ �� ������
���������� ������.

���. 5.20. ��������� ����������� ������ (����-�����)
����� Microsoft ������ ������� ���������� �������� ���������
���������� ������� � ���������� �� ����������� ���������� �� ��������
��� ����������� Windows NT/2000/XP ����� ������ ���������� ��� �������������
�������.
��� ��������� �������, � ������� ������ ��� ������������� ���������,
��� � ���������� � ����� � �������� "�����" ��������, � ���
��� ���� ����� ������������ ��� ��, ������������ ���������� �����, ������
������ ���� ��� �������� �� ��������� ���� � ��� ������ �������� �� ��
����������� ���������� ��������� ���. ��� �������� ���� � ���������� �������
������� �������� �������� �� ����� ����, � ������ ��� ������� ��� ������
���� ���������� �������, �������� ����� ����� � �������� �������������
�������� ���������.
������� ������������ ����� ������� ��� ������, � �������� ������ �����
�� ���� ��������� � ������� LRU (Leasr Recently Used).
����� ������ ������� ������ �������� ��� ���� ����������. ��������, ���������
������ ������ ������������ � ����������� ������ �������� ������� ���������,
� ��� ������ �������� ������ ��� ������ ��� ���� ��������� �����������
���� ������� �� �������. ��� ������� �������� ������� ��������� ��������
� � ���� �����, ��������, � [�������� 1987], ������������, ��� ��� �����
����������� ��������.
���������� ������������ � ��������� LRU �������� ��� ���������� clock-��������,
����������� �� ������ ����������� ��, � ��� ����� � �������� ���������
Unix. �� ������� � ��������� (���. 5.21).
- ���������� ������ �������� �������� ���, �����������,
��� � ������ �������� ���� ���������. ���� ��� �������� clock-�����.
- ��� ������ ��������� � ��������, � ������� clock-���
��� �������, ��������� ������ ������������� ���� ���.
- ���������, ������������ ������� ������, ����������
������������� ��� ����������� �������. ���� clock-��� �������, ������
�������� ����������� �������, � �������� ������������� �� ���������
����������� � ����� ��������. ���� clock-��� ����������, �� ���������
���������� ��� � ���������� �����.
���. 5.21. Clock-�������� (����-�����)
�������� clock, ��-��������, ���������� �� �������� �������� ��������
������������ ��������� � ��������� ������� ����� (���. 5.22). ��������
��� ����������� ��������� ������� ��� ��������, � ������� ����� ����������
���������, ����������� ����. ��������� ������� ����� ��������� �������
������, ��� � LRU: ������ �������� �� ������ ������ ���� ��� � ��������
��� �� ��� ������ ��������� � ��������, � ������ ��� ������ ���������
����� ������� "�������".

���. 5.22. ������ clock-���������
����������� ��� ��������� ������ ����������� ���������� ������ ������������
������������� clock-���������. ����� ���������� ������ � ����������� ��������
��� �������� ��� ���� � clock-��� � ������� �����������. ������� �����������
��������������� ��� ������ ������ � ��������/�������, � ����������� �������
���� ������� ��� �������.
�������� clock-���������
������ ������ ���������� VAX �� ����� ��������� �������������� clock-����.
BSD Unix �� ���� ����������� ���������� clock-��������, ��������� ���
����� ��� ���������� ��������.
�������� ������������ �������� ����������� ���� �������� ������ �������������
� ����� ������� ����� ���� ���������� � FIFO-���������� � ���������� VAX/VMS.
����������������� ������������ ����������, ��� �������� ������������������
������� �������� ����� ������� �� ������������ ��������� ������ ������.
���������� ���������� �������� �������� ������� � ���, ��� ������ ���������
����� ��������� ����� �������, ���������� �������
����������, ������� �� � ������ ������ ������������� �����. ������
������ ������ ������ ������� �� ��������� ���������, �� ���������� ��
��������� ������ ���������� � �. �.. �� � ����������� �������� �� �����
�������� ����� ������� ���.
���� ������� ����� ���������� �������� ����������� ����������� ������,
������� ���������� ������� ����� ����������. ��� �������� ������ ���������
����� �� ������ ������� ��������� ����� ��������, � ������������������
������� ��������������� ������. ��� ��������� ��-��������� ����������
thrashing (������������� �������� ��� �����
����� ���) � �������� ������ �������������.
� �������� ������������� ����������� ������ ������ ����� �������� ���,
����� ������� ������������� ���-�� ����� ����������, ����� ��� ���������
������ ���� ������� ��������� � ���, � ���������.
������ ��������� ����� ������������ ������������ � ����������� �� �����������
����� ��������� ���������� � ��������� ������ � ������, � ����� �� ������������
���������� ��������. �� ������ ������ ��������� ������������� ���������
����� ������ ���, ����� ����� ��������� ������ ��� �������� �� 50% [��������
1987].
��� ���� ������������ ������� ���������� � ������������ ����� Amdahl:
���������������� ������� ������ ����� �� ��������� ������ �� ������ MIPS
(Million of Instructions Per Second � ������� �������� � �������) ������������������
������������ ����������. ���� ������� �� ���������� ������, ������������
�� ���� �������, ���� ��������� �������, ��� ��������� ����� ��������
� �����������. ����� �������, ��� ��������, ��� �� ������ ������� ������
��� ����� ����� ��������� � ��������� ������ ������.
��� ������� ���� ���������� �� ������ ����� ������������ ������� �����������
���������� ���������, � �������� �� ������� ���������� ������ ������.
�������� �������� ���������� � ���� ������� ���� �������� �������� � ���������
������������� ����������� ������������ �����������, ������� � ������ �����������
���� �������� �������� � � ��, �������� ���������� ��� ����������� ������
� ����������� ������� � OS/2, Windows NT � ��������� ��������� Unix. �
����� ������, ��� ������ ������������ ��������� ������ ����� ����������,
������� ����� ����������� � �������, � ������ ���������� � ���.
� ����������� ������������ �������� ������������, ��� �������, ��������
� ������ ������ ������ � �����-����� �����������, � �������� � ����������
���� �������� ����������� ������� ����������� �������� �������. �������
� ����� �������� ������ ������ ������ � ������� �������, ���, ����� ���
������� ������������ ������� ��������� �������� ���� ������ �� ���������
� ������� ���. ������� ��� ����������� ���, ��� � ���� ����� ������������
������ ���������� ��� ������� � �������.
|