운영 체제 (Operating System) - Memory Management (2)

1. Page Replacement

이전 포스터에서 Demaind Paging을 다뤘는데, 필요할 때 VM을 Secondary storage에서 PM으로 로드하는 방식을 이용한다고 하였다. 하지만 User process가 사용하는 VM의 Page수보다 PM의 Frame 수가 적기 때문에 이미 할당된 PM의 Frame을 요구된 Page로 교체해줄 필요성이 생겼다. 이것이 Page replacement이다.  Page replacement는 PM에 위치한 Page를 Disk에 저장하고 요구된 Page가 해당 Frame을 할당 받도록 하는 방법이다. 이는 다음과 같은 순서로 진행된다.

디스크에서 요구된 Page의 위치를 찾는다 -> 물리 Memory에서 Free frame을 찾는다. (Free frame이 있다면 그대로 사용, 없다면 Page replacement algorithm을 사용하여 교체할 Victim frame을 선택하고 그걸 Disk에 저장 + Page table 변경한다) -> 요구된 Page를 Free frame으로 읽어들이고 해당 Page table을 적절히 변경 -> User processs를 재시작

Page replacement를 위해 고려해야할 사항에 어떤것이 있을까? Process에 어떻게 Frame을 분배할 것인가?(조금 사용중이면 많이 할당, 많이 사용중이면 적게 할당)를 위한 Frame allocation algorithm / 어떻게 교체할 Page를 고를것인가?를 위한 Page replacement algorithm이 있다. 결국 두 알고리즘에 적합한 알고리즘을 할당하여 I/O수행 횟수(혹은 page fault의 빈도)를 최소한으로 하고자 한다. 이제 위에 언급한 알고리즘의 예시를 확인해보자.

 

 

2. Page replacement algorihtm

2-1. Optimal Algorithm

필요없는 Page(오랫동안 사용되지 않을)를 먼저 교체한다. 하지만 이 기준은 알 수 없기 때문에 구현이 불가능하다.

 

2-2. FIFO Algorithm

멀티 미디어에 적합한 방식이다. (영상 생각해보면 이해가 쉽다)

 

2-3. SCR(Second Chance Replacement) Algorithm

기본적으로 FIFO와 같이 가장 오래된 Page를 replace하는 방식이다. 하지만 만약 그 Page가 최근에 사용되었다면, 그 Page의 최근 사용 flag를 0으로 만들고 건너뛴 후 다음 Page를 확인하는 것이다. 최근 사용 여부는 Reference bit로 기록되며, Page참조 때 1으로 설정되고 일정 주기마다 0으로 reset된다. 하지만 가장 오래된 Page가 참조가 주기적으로 계속 들어올것임에도 불구하고 Second change를 받은 이후에도 계속 가장 먼저 체크되므로 교체된다는 문제가 있다.

 

2-4. Clock Algorithm

원형 Queue를 사용하는 SCR기법의 발전형으로 다음에 제거될 Page를 가리키는 Hand pointer를 이용하여 page를 고체하는 방식이다. 교체 Page의 Reference bit를 확인하고 1이라면 0으로 설정 후 hand pointer를 다음으로 이동시켜 그 Page가 나중에 다시 체크되도록 만든다.

 

2-5. LFU(Least Frequently Used) Algorithm

가장 사용빈도가 적은 Page를 교체하는 방법이다. 괜찮은 성능을 보이지만, 이 빈도가 계속 유지되므로 실행 초기에 많이 사용된 Page가 이후 사용되지 않더라도 Frame을 계속 차지하는 문제가 존재한다.

 

2-6. NRU(Not Recently Used) Algorithm

최근에 사용하지 않은 Page를 교체하는 방법이다. 여기에 추가로 참조를 체크하는 참조 Bit와 데이터 변형을 체크하는 변형 Bit를 두어 관리한다. 이 알고리즘의 인사이트는 참조보다 변형일 때 다시 사용될 확률이 높다는 것이다. 따라서 다음과 같은 우선순위로 교체된다.

 

2-7. LRU(Least Recently Used) Algorithm

가장 오랜 시간 참조되지 않은 Page부터 먼저 교체하는 알고리즘이다. 이는 Locality를 고려한 Replacement algorithm으로, Optimal algorithm과 유사한 결과를 도출한다고 한다. 이에 대한 구현은 Counter의 사용하여 구현하는 방식과 Queue를 이용해 구현하는 방법이 있다. Queue에서 방금 사용한 Page를 Queue의 가장 위로 이동시키면 가장 아래에 오래된 Page가 갈 것이다. 

 

2-8. Swapping

Page replacement algorithm을 이용해서 메모리를 교체하기에는 Page fault가 너무 많이 났다고 한다. 그래서 이 Page Out으로 해결하지 못하는 부족한 Memory를 Process가 차지하는 메모리 전체를 Swap out함으로써 해결하고자 한 것이 이 기법이다. 이렇게 Page out이나 Swapping에 사용되는 Secondary storage(Backing store)를 Swap영역이라고한다.

 

 

3. Countigous Memory Allocation

프로그램에 메모리를 어떻게 할당해주어야 할까? 우선 <1 Single partition allocation>과 같이 단순하게 User program영역을 한 번에 1개의 User program만 사용하도록 하는 방법이 있다. 그리고 Multiprogramming이 등장하면서 여러개의 프로그램을 동시에 메모리에 올릴 필요성이 생기면서 <2 Multiple partition allocation>와 같이 올라가게 되었다. 하지만 User program이 너무 많아지면서 <2>로는 모든 프로세스를 올릴 수 없게되어 <3 No partition>처럼 각 프로그램의 필요에 따라 일부를 전체 User program에 올리는 방식이 등장하였다. <3>의 경우 Page out / Swap out 시 Garbage collection을 필요로 한다.

 

이렇게 메모리에 올리면서 어떠한 문제점이 있을까? 프로그램이 로드될 수 있는 메모리 중 가장 먼저 찾은 것(First-fit)에 올릴수도, 아니면 크기가 크면서 가장 비슷한 것(Best-fit)에 올릴수도, 아니면 크기가 가장 큰 것(Worst-fit)에 올릴 수도 있을 것이다. 

이 배치가 왜 중요할까? 바로 fragmentation 때문이다. Fragmentation은 2가지로 나뉠 수 있다. 총 공간은 충분하지만, 연속된 빈 공간이 없어서 메모리를 활용할 수 없는 External framentation와 Memory를 성공적으로 할당했지만, Paging 등으로 인하여 필요 이상으로 할당한 부분(사용하지 못하는)인 Internal fragmentation이 있다.  External framentation을 해결하기 위해 Paging이 등장하였다. Internal fragmentation을 위해 Paging이 등장한 현제에도 해결하지 못한 문제이다. 따라서 Page의 크기에 대한 고려가 중요하다.

 

 

4. Protection과 Relocation

User program이 OS의 메모리주소에 접근하면 안되는 Protection과 프로세스 실행 시 물리 메모리의 어느 부분에 올라가더라도 Code의 주소를 결정할 수 있어야 하는 Relocation을 제공해주어야 한다. 이는 HW(Limit register와 Relocation register)로 구현 된다. 그 하드웨어에 대한 내용은 다음과 같다