메모리가 가득 차있을 때, 어떤 기존 페이지와 새로운 페이지를 교체할 것인가?
우선 가장 단순하고 기본적인 방법은 FIFO이다.
가장 먼저 들어온 Page를 빼고 새로운 Page를 넣는 방식이다.
가장 좋은 방법은, 이후에 가장 덜 쓸 페이지를 교체하는 것(OPT - OPTimal)인데,
이후에 가장 덜 쓸 페이지가 무엇인지 어떻게 알 수 있는가? 이는 현실적으로 불가능하다.
그래서 OPT가 아닌 그나마 괜찮은 성능의 알고리즘들이 개발되어왔다.
가장 오래 전에 사용된 페이지를 교체하는 방식이다.
LRU알고리즘이 가장 많이 사용되는 알고리즘이고,
메모리 지역성이 낮은 페이지 부터 교체해나가는 방식을 의미한다.
메모리 지역성의 원리
CPU가 새 명령어가 필요하여 메모리에 적재해야 할 때,
‘최근에 사용했던 메모리의 “근처(adjacent)” 에 있는 것을 참조할 가능성’을
메모리 지역성이라 한다.
즉, 프로세스 내의 명령어 및 데이터 참조가 ‘군집화’ 성향을 띈다는 의미이다.
LRU의 구현 방법은 여러가지가 있다.
LinkedList, Queue 등 다양한 자료구조로 구현이 가능할 것 같다.
관련 알고리즘 문제들도 PS사이트에 많이 있다.
(예 : 프로그래머스 캐시 문제)
가장 적게 사용된 페이지를 교체하는 방식이다.
LRU와 마찬가지로 가장 오래 전에 사용된 페이지를 교체하는 방식이나,
‘가장 오래된’의 기준을 ‘읽기(R)’와 ‘쓰기(M)’로 비트 구분(R,M)하여 페이지를 교체.
즉, (0,0)을 시작으로 읽었으면 (1,0), 썼으면 (0,1), 읽고 썼으면 (1,1)로 표시하여
(0,0) -> (0, 1) -> (1, 0) -> (1, 1) 의 순서대로 교체하는 알고리즘이다.
읽고 썼으면 가장 최근에 가장 많이 이용했다는 의미가 되므로 가장 마지막 순서가 된다.
LRU보다 조금 더 디테일한 기준으로 페이지를 교체하는 방식이다.
페이지 폴트가 빈번하게 발생하여 과도하게 페이지 교체 작업이 일어나면,
실제 CPU동작은 하지 못하고 페이지 교체만 발생하게 되어
결론적으로 아무것도 실행하지 못하는 상황을 의미한다.
페이징 기법과는 다른 또 다른 가상메모리 기법이다.
가상메모리를 서로 크기가 ‘다른’ 논리적 단위인 세그먼트(Segment)로 분할하는 기법이다.
페이징은 리눅스에서는 4KB로 분할하는 반면, 세그먼트는 조각의 크기가 4KB로 고정되지 않는다.
단위를 Code Segment, Data Segment, Stack Segment, Extra Segment 등으로 하여 나눈 후 메모리에 접근한다.
세그멘테이션 또한, Segment Table을 만들고, v = (세그먼트 번호, 변위) 와 같이 가상메모리와 실 메모리에 접근한다.
페이징은 고정된 4KB의 용량을 가진다 - 따라서, 페이지 블록만큼 데이터가 딱 맞게 채워져 있지 않을 때 공간이 낭비된다.
반면, 세크멘테이션에서는 세그먼트마다 크기가 다른데,
실제 물리메모리가 세그먼트가 요구하는 원하는 크기를 제공하지 못하는 경우가 발생한다.
즉, 내부 단편화와 외부 단편화의 해결 방법은 각각 세그먼트/페이징 이나,
각각의 두 기법이 또한 각각 외부단편화/내부단편화 문제를 발생시키는 아이러니가 있다.
참고로, 리눅스는 페이징 기법을 기반으로 구현되어있다.
int main(){
fd = open("data.txt", O_RDONLY);
if(fd == -1){
printf("파일을 열지 못했음");
return 1
}else{
printf("파일을 열었음");
return;
}
}
위 내용은 ‘패스트캠퍼스’의 컴퓨터공학 강좌 내용을 요약 정리한 것임을 밝힙니다. (https://www.fastcampus.co.kr/)