77-30569/342072

-

77 - 30569. 0421100025. ISSN 1994-0408

77-30569/342072
# 04, 2012
.. , ..
004.451.43:004.451.352
. .. v.semenov@ivideon.ru, kva@bmstu.ru

- . Linux .
Linux LRU ( ) PFRA [1]. , [2].
, Linux.
. . 1 . . 2 , . 3 Linux. , . 4 .
1. Linux
, N , N + 1 , LRU - , (. 1).
t t+1 t+2
t+K
:
:

> f \ f \ t f
N N+1 0 ... N
:
. 1.
N + 1
LRU , , PN-1 P0. , , P0. P1 »» ..
, . . 2 . , . Linux 2.6.28 128 .
. 2, LRU-- 100% .

S
I

I ^

2
25
20
15
10

- --
-
-
80 90 100 110 120 130 140 , %
150
160
. 2.
5
0
: (4 ) . 110% .
2.
:
, ;
;
.
0 . 3. , ( ) .


. 3.
. , .
.
, - . :
;
, .
, . . , . 4.
- :
, ;
, ;
"" (.. / );
, , .
, , - , . , . , , . , »» , .
, . , , Linux PFRA LRU.
, , .
. 4.
, .
:
, ;
, , , .
3.
. Linux 2.6 handle_pte_fault().
, . handle_pte_fault mm_struct , . .
, , , .
, , , , , LRU PFRA. , :
struct loop_info {
unsigned long start_address; unsigned long end_address; unsigned long last; unsigned long period; unsigned long pages_present; unsigned long bad;
};
pages_present , . .
, , . , loop_info. , :
scans Jist ;
loops_list .
.
handle_pte_fault , , . , , current.
address .
current-»loops_list. address address == loop-»start, : .
, current-»scans_list. address == cycle-»end + 1, . , :
address == scan-»start, ;
address » scan-»start && address << scan-»end, address.
, address , current_scan. , . , current_scan , current_scan scans Jist. address.
, , scan_proc loop_proc, , . : , .
recent. , . , LRU, .
, bad.
4.
, . OpenSSL, boost::graph MATMUL.
, , 500 . PostgreSQL 9.0. Linux GCC 4.4.
QEMU 0.12.0 64, 128, 256, 512 . Debian Linux 2.6.28. Ubuntu Desktop 11.04, 4 Intel Core2 Quad-8200.
, , boost::graph. . , . . 5, boost::graph 6%.
S
I

I ^
.

320
300
280
260
240
220
200
1ST
- - -
180
0 50 100 150 200 250 300 350 400 450 500 550 ,
. 5. : boost::graph
- . 6, .
+ 180 , (. 7).
I

I ^
.


2800
2600
2400
2200
2000
1800
1600
1400
- - -
I

I ^
.


3600 3400 3200 3000 2800 2600 2400 2200 2000 1800
50 100 150 200 250 300 350 400 450 500 550 ,
. 6. -:
- - -
50 100 150 200 250 300 350 400 450 500 550 ,
. 7. : + PostgreSQL
OpenSSL + MATMUL + . . 8. ( 27%) , .
0
0
H >
I
s z
s
I

I ^

- m

D
65 60 55 50 45 40 35 30 25 20
II
N, -43- -
-
- -
- N *4 X
- \ 4 N -
ii
50 100 150 200 250 300 350 400 450 500 550 ,
. 8. : + +

, . 27% . 6%.
0

1. BovetD., Cesatti M.Understanding the Linux Kernel, Third Edition. O'Reilly Media, 2005. 944 p.
2. O'Neil E.J., O'Neil P.E., Weikum G. The LRU-K Page Replacement Algorithm for Database Disk Buffering//Proceedings of the 1993 ACM SIGMOD Conference, 1993. Pp. 297-306.
electronic scientific and t echnical periodical
SCIENCE and EDUCATION
El FS77 - 30569. 0421100025. ISSN 1994-0408
Page frame reclaiming method with scanning access detection
77-30569/342072
# 04, April 2012
V.N. Semenov, V.A. Krischenko
Bauman Moscow State Technical University v.semenov@ivideon.ru, kva@bmstu.ru
We describe problems with the current LRU-based page reclaiming algorithm used by Linux kernel that arise in the case of a regular memory access pattern. Based on the results of some preliminary experiment, a pattern detection method is proposed. The method uses page fault history as an input. The developed reclaiming algorithm and its implementation for Linux kernel are described. Experiments results with the method software implementation of this algorithm are presented.
References
1. BovetD., Cesatti M. Understanding the Linux Kernel, Third Edition. O'Reilly Media, 2005. 944 p.
2. O'Neil E.J., O'Neil P.E., Weikum G. The LRU-K Page Replacement Algorithm for Database Disk Buffering//Proceedings of the 1993 ACM SIGMOD Conference, 1993. Pp. 297-306.