가변 크기 페이지가있는 버퍼 풀. 수신 페이지가 축출 페이지보다 클 때 페이지를 합체하는 고성능 방법이 필요합니다.

Question

데이터베이스 버퍼 풀 (메모리 풀)의 구현에서 메모리의 페이지로 구성된 버퍼가 있습니다.

페이지 크기가 다릅니다 (512kb의 정수 배수).

내 퇴거 정책은 LRU (가장 최근에 사용되지는 않았지만)이지만 퇴거하려는 페이지의 크기가 교체해야하는 것보다 적습니다. LRU도 따르고 싶으면 다음과 같이 많은 LRU 페이지를 제거해야합니다. 내 새 페이지에 꼭 들어 맞아야합니다.

내가 축출하기 위해 최근에 사용한 페이지 n이 필요하다고 가정합니다. 그러나이 페이지는 반드시 버퍼/메모리 풀에서 연속적 일 필요는 없습니다.

간단한 접근 방법은 이러한 n 페이지를 통합하는 것입니다. 즉, 버퍼 풀을 적절히 재정렬해야한다는 의미입니다.

가장 간단한 방법은 전체 버퍼를 복사하고 영구 버퍼를 덮어 쓰고 데이터 형식을 적절하게 업데이트하는 것입니다. 그러나 이것은이 작업을 위해 전체 버퍼를 복사하는 데 충분한 RAM이 있다고 가정합니다. 전체 버퍼를 복사 할 필요가없는 영리한 접근법이 있습니까?

감사

Answer 1

당신이 주변에 버퍼를 이동해야하자마자, 그것은 그러나 내 의견 "고성능"을,하지 않을 방법이에 대한 :

당신이 퇴거하고자하는 페이지를 k 번 페이지 크기 512KB, 즉 들어오는 페이지의 크기입니다.

|X1 |1  |2 |X2 |3  |4  | 

두 X ES가 퇴거 할 수있는 페이지입니다 :

최악의 레이아웃 (바 |) == 512 킬로바이트를 제외한 네 문자()이 같은입니다. 이제 버퍼를 연속으로 만들려면 X2을 X1 (또는 다른 방법으로) 옆으로 이동해야합니다. 내 접근 방식은 오른쪽에 X1 후 페이지를 이동하는 것입니다 (안으로 X2)에 장소. 우리는 X2을 무시하는 것이 안전합니다. 왜냐하면 우리가 어쨌든 그것을 퇴거시키고 싶어하기 때문입니다.

그런 식으로 전체 버퍼를 복사하는 대신 3 페이지 크기 만 업데이트하면됩니다.

|X1 |1 |2  |X2 |3  |X3  |4  |5 | 

하나는 여전히 위에서 순진 알고리즘을 사용할 수 있지만, 최적화의 가능성이 있습니다

더 복잡한 문제가 될 것입니다. 예를 들어 2을 터치하지 않고 1을 X2으로 안전하게 이동할 수 있습니다. 2도 마찬가지이며 X3으로 이동할 수 있습니다.

실제로 동적 배열 삽입 및 스와핑으로 알려진 단순한 이동 기술을 사용할 수는 있지만 가능한 최적화를 확인하는 것이 좋습니다.이 경우 이동해야 할 페이지를 열거하십시오. 순진한 알고리즘을 사용하고 먼저 추방 대상 공간에 직접적으로 맞추어보십시오. 실패한 후에 만 ​​(첫 번째 예와 같이) 이동을 사용해야합니다.

원 자성이 필요한 경우 전체 버퍼를 복사해야합니다. 이 경우 위에서 설명한 최적화 된 방법도 사용할 수 있지만 제거되는 페이지에 들어갈 수있는 페이지에 맞지 않는 한 문제가 발생합니다. 이 경우 퇴거 알고리즘을 재귀해야 적절한 장소를 찾을 수 있으며 더 많은 페이지를 추방 할 수 있습니다.