pintOS의 가상메모리 커리큘럼이 지나갔다.
이번주차를 정리하면서 우리팀이 자료를 매우 깔끔하게 만들어서 이를 이용해서 WIL를 써보려고 한다.
Page replacement
우리는 가상메모리라는 추상화를 통해서 무한한 메모리라는 환상을 만드는 것이 11주, 12주차의 주 목표였다.
무한한 메모리를 실현하기 위한 방식은 크게 Virtual address space partitioning, page fault, Page replacement방식이 있다.
이 세가지 중 우리팀은 page replacement에 대해 집중해서 정리해서 주차 발표를 위해 내용정리를 해보았다. page replacement는 page fault가 발생하고 필요한 페이지가 물리 메모리에 없을 때, 운영 체제는 새로운 페이지를 받아오기 위한 공간을 만들기 위해 어떤 페이지를 교체할지 결정하는 방식이다.
가상 메모리는 디스크 스왑을 통해 실제의 DRAM 용량보다 큰 메모리 공간을 사용할 수 있지만, 디스크 in/out 작업은 디스크의 물리적 특성과 작업의 복잡성 때문에 많은 시간과 비용이 소모된다. 따라서 적절한 페이지 교체 알고리즘 사용하여 스왑 비용을 최소화하여 가능한 효율적인 교체가 이루어지도록 OS단에서 설계해야한다.
page replacement algorithms
이를 위해 다양한 page replacement 알고리즘이 개발되었으며 관해서 다음 짧게 소개하겠다.
page replcement 알고리즘은 다음과 같이 크게 FIFO, LRU, LFU, random, optimal 등이 있다.
최근에는 LRU, LFU가 많이 사용되고, 이 외에도 기본적인 FIFO, 페이지를 무작위로 선택하는 random, 모든 페이지 접근 시점을 미리 알고 있다면 사용하는 optimal 방식이 있다.
우리는 이 알고리즘 중 LRU를 선택해서 구현했다.
아래에는 자료 정리하면서 더 자세히 알아봤던 내용들이다.
-
<참고 내용>
-
FIFO
FIFO(First-In, First-Out) 알고리즘은 페이지 교체 알고리즘 중에서 가장 간단하고 기본적인 알고리즘입니다. FIFO 알고리즘은 먼저 메모리에 적재된 페이지를 먼저 교체하는 방식으로 동작합니다. 따라서 가장 오래된 페이지가 교체 대상이 됩니다.
FIFO 알고리즘은 구현이 간단하고 오버헤드가 적어서 많은 운영 체제에서 사용되었으며, 여전히 일부 시스템에서 사용되고 있습니다. 그러나 FIFO 알고리즘은 페이지의 접근 패턴을 고려하지 않기 때문에 페이지 교체의 품질이 다른 알고리즘들에 비해 낮을 수 있습니다. 특히, 페이지의 사용 빈도가 다른 페이지들과 크게 다를 경우 교체 효율이 저하될 수 있습니다.
실제로 FIFO 알고리즘은 최근에 사용되는 더 효율적인 페이지 교체 알고리즘들에 비해 상대적으로 사용량이 줄어들었습니다. LRU(Least Recently Used), LFU(Least Frequently Used), OPT(최적 교체) 등의 알고리즘이 FIFO에 비해 더 많이 사용되고 있습니다. 그러나 FIFO 알고리즘은 간단하고 예측 가능한 동작으로 인해 몇몇 특정 상황에서 성능이 좋을 수 있습니다. 따라서 특정 시스템이나 요구 사항에 따라 FIFO 알고리즘이 선택될 수 있습니다. -
벨라디의 이상현상
벨라디의 이상 현상은 페이지 교체 알고리즘 중 FIFO (First-In-First-Out) 알고리즘에서 발생할 수 있는 현상입니다. 이 현상은 페이지 부재가 빈번하게 발생하며, 페이지 프레임 수를 늘려도 성능이 개선되지 않는 상황을 의미합니다.
벨라디의 이상 현상은 다음과 같이 발생합니다. 가정해보겠습니다. 시스템에는 3개의 페이지 프레임이 있고, 주어진 시간 동안 다음과 같이 페이지가 요청되는 경우를 고려해봅시다:
페이지 A 요청
페이지 B 요청
페이지 C 요청
페이지 A 요청
페이지 D 요청
페이지 B 요청
페이지 E 요청
FIFO 알고리즘은 가장 오래된 페이지를 교체하는데, 위의 시나리오에서는 페이지 A, B, C가 먼저 할당되고, 이후에 다시 페이지 A가 요청되는 순서입니다. 이 경우, FIFO 알고리즘은 가장 오래된 페이지 A를 교체합니다. 하지만 페이지 A는 다시 요청되기 때문에 교체 후 다시 메모리에 로드됩니다. 이러한 상황에서는 페이지 부재가 빈번하게 발생하고, 페이지 프레임 수를 늘려도 성능이 개선되지 않는 현상이 벨라디의 이상 현상입니다.
이러한 이유로 FIFO 알고리즘은 벨라디의 이상 현상이 발생할 수 있는 단점을 가지고 있습니다. 이를 개선하기 위해 LRU (Least Recently Used) 또는 Optimal 알고리즘 등의 다른 페이지 교체 알고리즘을 사용할 수 있습니다. -
LRU
LRU(Least Recently Used)는 페이지 교체 알고리즘 중에서 가장 널리 사용되는 알고리즘 중 하나입니다. LRU 알고리즘은 페이지의 최근 사용 여부를 기반으로 페이지를 교체하는 방식으로 동작합니다.
LRU 알고리즘은 메모리에 적재된 페이지들 중에서 가장 오랫동안 사용되지 않은 페이지를 교체하는 원리입니다. 페이지에 접근이 발생할 때마다 해당 페이지를 최신으로 갱신하여 최근에 사용된 페이지를 추적합니다. 교체가 필요한 상황에서는 가장 오래전에 사용된 페이지를 선택하여 교체합니다.
LRU 알고리즘은 페이지의 접근 패턴을 고려하여 교체를 수행하기 때문에 교체의 정확성과 성능 면에서 우수한 알고리즘으로 알려져 있습니다. 최근에 사용된 페이지들은 교체되지 않고 메모리에 유지되는 경향이 있기 때문에 Locality(지역성) 원리에 잘 부합합니다. 일반적으로 실제 시스템에서도 LRU 알고리즘이 많이 사용되고 있습니다.
하지만 LRU 알고리즘은 페이지 접근 패턴을 추적하기 위해 추가적인 자료 구조와 연산이 필요하므로 구현 비용이 높을 수 있습니다. 또한, 페이지 접근 패턴이 예측하기 어려운 경우에는 교체 성능이 저하될 수 있습니다. 이러한 이유로 실제 시스템에서는 LRU의 근사 알고리즘인 Clock 알고리즘 등이 사용되기도 합니다. -
LFU
LFU(Least Frequently Used)는 페이지 교체 알고리즘 중 하나로, 페이지의 사용 빈도를 기반으로 페이지를 교체하는 방식입니다.
LFU 알고리즘은 각 페이지의 사용 빈도를 추적하여 가장 적게 사용된 페이지를 교체하는 원리로 동작합니다. 페이지에 접근이 발생할 때마다 해당 페이지의 사용 빈도를 증가시킵니다. 교체가 필요한 상황에서는 가장 적게 사용된 페이지를 선택하여 교체합니다.
LFU 알고리즘은 페이지의 사용 빈도를 정확하게 추적하여 교체를 수행하기 때문에 최근에 적게 사용된 페이지들이 교체되는 경향이 있습니다. 이는 특정 페이지가 장기간 사용되지 않을 경우 교체되는 것을 보장합니다.
하지만 LFU 알고리즘은 페이지의 사용 빈도를 추적하기 위한 추가적인 자료 구조와 연산이 필요하므로 구현 비용이 높을 수 있습니다. 또한, 페이지 접근 패턴이 예측하기 어려운 경우에는 교체 성능이 저하될 수 있습니다. -
optimal
Optimal 페이지 교체 알고리즘은 가장 이상적인 페이지 교체 알고리즘으로도 알려져 있습니다. Optimal 알고리즘은 페이지 교체 시 가장 오랫동안 사용되지 않을 페이지를 교체하는 방식입니다.
Optimal 알고리즘은 현재 시점에서 앞으로 가장 오랫동안 사용되지 않을 페이지를 선택하여 교체합니다. 이를 위해 알고리즘은 모든 페이지 접근 시점을 미리 알고 있어야 합니다. 모든 페이지 접근 시점을 미리 알고 있다면, 가장 오랫동안 접근이 없을 것으로 예상되는 페이지를 교체합니다.
Optimal 알고리즘은 이론적으로 가장 효율적인 페이지 교체 알고리즘이지만, 실제로 구현하기에는 매우 어렵고 비현실적입니다. 이는 알고리즘이 앞으로 발생할 페이지 접근 시점을 미리 알아야 하기 때문입니다. 실제 운영 체제에서는 앞으로 발생할 페이지 접근을 예측하기 어렵기 때문에 Optimal 알고리즘을 실제로 사용하기는 어렵습니다. -
RANDOM
Random 페이지 교체 알고리즘은 페이지를 무작위로 선택하여 교체하는 방식입니다. 각 페이지에 대해 교체될 확률이 동일하게 유지되며, 이전 페이지 접근 기록이나 사용 빈도에 대한 정보를 고려하지 않습니다.
Random 알고리즘은 간단하고 직관적이지만, 페이지 교체의 품질을 보장하지 않습니다. 이 알고리즘은 무작위성에 의존하기 때문에 어떤 페이지가 교체될지 예측할 수 없습니다. 때문에 최적의 페이지 교체를 보장하지 않을 수 있으며, 다른 알고리즘들보다 성능이 낮을 수 있습니다.
Random 알고리즘은 간단하고 구현하기 쉬우며, 페이지 접근 패턴에 대한 정보가 없는 경우나 균등한 확률 분포를 원하는 경우에 사용될 수 있습니다. 그러나 실제로는 페이지 접근 패턴을 고려하는 다른 알고리즘들이 더 나은 성능을 보이는 경우가 많습니다.
요약하자면, Random 알고리즘은 페이지를 무작위로 선택하여 교체하는 방식입니다. 간단하고 구현하기 쉽지만, 최적의 페이지 교체를 보장하지 않고 다른 알고리즘들보다 성능이 낮을 수 있습니다.
다음은 page replacement 및 LRU를 구현하면서 사용했던 페이지 엔트리관련 비트들에 대해 간략하게 요약해보았다.
Valid bit
Valid bit는 페이지 테이블 엔트리에서 사용되는 비트로, page가 물리메모리와 매핑되어있다면 1, 매핑되어있지 않다면 0으로 표시되어어야 한다. 참고로 핀토스에서는 PTE_P라는 변수명으로 present bit로 표시되어 있다. 페이지 폴트는 present bit가 0인 페이지에 접근하는 과정이므로, Paging_init함수와 mmu.c 파일의 pml4와 관련된 함수 등의 가상주소와 물리주소를 매핑하는 모든 과정에서 사용된다.
[ PTE_P 사용함수 : ]
- present bit가 0인 페이지에 접근하는 과정이 페이지 폴트!
-
Paging_init : main 함수에서, 메모리 시스템을 초기화 할 때 사용되는 함수.
- palloc_init 함수가 메모리 크기를 결정하면, paging_init이 결정된 크기만큼 페이지 테이블을 초기화하고 메모리 매핑을 수행.
- 이 때, PTE_P를 사용하여 페이지 테이블 엔트리가 유효함을 나타냄.
-
mmu.c 파일 → pml4 관련 모든 함수 : 마찬가지로 pml4 관련 모든 함수들에서 페이지 테이블 엔트리의 유효성을 표현할 때 valid bit를 사용.
- valid bit는 페이지 테이블에서 가상주소와 물리주소를 매핑하는 모든 과정에서 사용됨.
access bit
Access bit는 페이지 교체 알고리즘에서 최근에 읽기 또는 쓰기 작업에 의해 접근되었는지 여부를 확인하기 위한 비트다. 물리메모리의 frame이 이미 모두 매핑되어있다면 LRU정책에 맞춰 가장 오랫동안 사용되지 않은 페이지와 매핑된 frame을 swap out을 통해 희생시키고 실행시킬 frame을 swap in해줘야한다.
핀토스에서는 vm_get_frame, vm_evict_frame, vm_get_victim이 차례로 해당 로직에 관여하며,
vm_get_victim함수에서는 for문으로 frame_list를 차례로 돌면서 pml4_is_accessed함수를 통해 이미 접근한 기록이 있는 pte는 비트를 0으로 바꾸면서 지나가고, 접근 기록이 없는 pte가 나왔을 때 해당 페이지를 victim(희생양)으로 선택하여 리턴함으로써 LRU가 구현되도록 했다.
- <참고 내용>
[ PTE_A 사용 함수 : vm_get_frame → vm_evict_frame → vm_get_victim ]
- vm_get_frame : 물리메모리에서 페이지를 할당받는 함수. 이 때 모든 물리메모리의 프레임이 사용 중인 경우, 제거할 frame을 정해야 함. (vm_evict_frame 호출)
- vm_evict_frame : 삭제할 프레임을 결정한 후, 실제로 페이지를 하드디스크로 스왑 아웃. 여기서 삭제할 프레임을 결정하기 위해 다시 vm_get_victim을 호출
- vm_get_victim : 삭제할 프레임을 결정하는 함수!!
- pml4_is_accessed : 주어진 pml4와 가상주소를 기반으로 해당 가상페이지가 접근(access)되었는지 확인하는 함수. PTE가 존재하고, 해당 엔트리의 accessed bit가 설정되어 있다면(1) true 반환
- pml4_set_accessed : 해당 가상페이지의 accedssed bit를 설정하거나 해제하는 함수
- vm_get_victim에서 Accessed Bit를 사용해 페이지 교체 알고리즘을 구현할 수 있음. 우리 팀은 LRU 방식으로 구현함. for문으로 frame_list를 차례로 돌면서 사용(접근)하지 않았던 페이지를 골라냄. pml4_is_accessed로 이미 접근한 기록이 있는 pte는 비트를 0으로 바꾸면서 지나가고, 접근 기록이 없는 pte가 나왔을 때 해당 페이지를 victim(희생양)으로 선택하여 리턴함.
dirty bit
Dirty bit(더티 비트)는 페이지의 수정 여부를 나타내는 비트다. DISK in/out을 하는데에는 많은 cost가 소비된다. 이를 줄이기 위해서 페이지가 수정되었을 때만 swap out이 진행되도록 하는 비트다. 관련된 함수는 do_munmap, file_backed_swap_out함수로 dirty bit가 1일때 수정된 내용을 디스크에 업데이트하고 더티비트를 0으로 초기화 한다.
- 참고 내용
[ PTE_D 사용 함수 : do_munmap & file_backed_swap_out ]
-
do_munmap : 주어진 가상주소 범위의 메모리 매핑을 해제하는 함수.
- while문을 사용해, PGSIZE씩 addr를 늘려가면서, 각 addr에 대응되는 페이지의 uninit 필드에 저장된 aux를 가져옴(container). (가져온 구조체에는 페이지와 관련된 추가 정보들이 저장되어 있음.)
- pml4_is_dirty : 만약 페이지에 대응하는 pml4의 엔트리가 존재하고, Dirty bit가 설정된 경우(수정된 이력이 있는 경우),
- file_write_at : 수정된 내용을 디스크에 업데이트하고,
- pml4_set_dirty : 더티 비트를 0으로 초기화해 줌.
- pml4_clear_page : 이 후, 현재 프로세스의 pml4에서 해당 가상주소에 대응하는 PTE를 제거!
-
file_backed_swap_out : File_backed page를 스왑 아웃하는 함수.
- 주어진 페이지의 uninit 필드에 저장된 aux(container) 를 가져온 후,
- pml4_is_dirty 함수로 해당 페이지의 dirty bit를 확인하고,
- file_write_at 함수로 수정된 페이지의 내용을 파일에 기록함.
- pml4_set_dirty 함수로 pml4 엔트리의 더티 비트를 0으로 초기화
- pml4_clear_page 함수로 현재 프로세스의 pml4에서 해당 가상주소에 대응하는 PTE를 제거!
-
Dirty Bit : 페이지 변경 여부 저장하는 비트. 변경될 때마다 해당 비트는 1이 되고, 디스크에 변경 내용을 기록하면 0으로 초기화 됨.
-
do_munmap 과 file_backed_swap_out에서 더티 비트는 비슷한 플로우로 사용됨.
-
어떤 페이지가 Swap Out 될 때, 해당 페이지가 수정되지 않았다면 스왑 아웃할 필요가 없음. 동일한 내용이 Disk 어딘가에 있기 때문임.
따라서, 페이지의 수정 여부를 알 수 있다면, 페이지를 교체할 때 스왑 아웃 시간을 절약할 수 있음. (Swap In 만 해주면 되기 때문)
이 때, 페이지의 수정여부를 알려주는 값이 바로 Dirty Bit임!
