페이지 걷기 알고리즘에 대한 도움이 필요합니다.

Question

나는 내 자신의 운영 체제를 작성 중이며 더티 비트가 설정되었는지 여부를 확인하려고합니다. 그래서 나는 특정 가상 주소 범위를 따라 걷고 싶다 R! R2를하고 페이지를 살펴보고 설정을 확인하십시오. 나는 이것을 수행하기위한 좋은 알고리즘을 찾고 있습니다. 각 페이지 테이블 수준을 트리 수준으로 처리하고 각 수준을 살펴볼 수 있습니다. 그래서 DFS 나 BFS를 사용할 수 있습니다. 이 작업을 수행하는 데 더 좋은 알고리즘이 있습니까?

Answer 1

각 항목을 확인하려면 depth first search을 사용하십시오. DFS는 트리의 레벨 수보다 더 깊은 스택을 필요로하지 않으며 페이지 테이블은 몇 레벨 수준에 불과합니다.

BFS는 느리고 requires additional storage입니다. 너비 우선 속성을 사용하면 일찍 탈출 할 수있을 때 일반적으로 가장 유용합니다.