[OS] Memory Management II

Page Replacement

• Memory 과다 할당 상태 (Over Allocation of Memory)
  • 발생 원인: Multi Programming System에서 메모리 내 사용자 프로세스 수가 증가함에 따라 발생
    • 개인 PC같은 메모리가 크지 않은 상황에서 흔히 발생
  • 상황: 모든 User Process가 사용하는 Page 수보다 물리 메모리의 Frame 수가 적은 상황
  • 해결 방법: Page Fault 처리에 Page Replacement를 추가하여 해결

 

Page Replacement

• 물리 메모리에 위치한 Page를 Disk(보조 저장 장치)에 저장하고 (Page Out), 요구된 Page가 해당 Frame을 할당받도록 하는 방법 (Page In)
• 과정
  1. 디스크에서 요구된 Page의 위치를 찾는다.
  2. 물리 메모리에서 Free Frame을 찾는다.
     • Free Frame이 있다면 사용
     • 없다면, Page Replacement Algorithm을 사용하여 교체할 Frame(Victim Frame)을 선택
     • 교체할 Victim Frame을 Disk(Swap Out)에 저장하고, Page Table을 변경
  3. 요구된 Page를 2단계에서 선택된 Free Frame으로 읽어 들이고(Swap in), 해당 Page Table을 적절하게 변경 (valid-invalid bit == Present bit 변경 )
     • Valid(v) = Present(1): 이 페이지는 지금 물리 메모리(RAM)에 있다.
     • Invalid(i) = Not Present(0): 이 페이지는 지금 메모리에 없고 디스크(Swap Area)에 있다.
       • 그러니 지금 읽으려고 하면 Page Fault(오류)를 내서 멈춰야 한다.
  4. User Process를 재시작한다.

Basic Page Replacement 도식

• 고려 사항
  • Frame Allocation Algorithm: 각각의 User Process에게 어떻게 Frame을 분배해 줄 것인가?
  • Page Replacement Algorithm: Page 교체가 필요할 때 어떻게 교체할 Page를 고를 것인가?
  • 목표: Page 교체에 의한 I/O 작업 수행 횟수를 최대한 줄이는 것
    • 이유: I/O 작업은 매우 큰 비용을 사용하며, 이는 System의 성능을 크게 좌우하는 요소이기 때문

 

Page Replacement Algorithms

• 가장 낮은 Page Fault 발생 빈도를 가진 Algorithm, 즉 가장 낮은 I/O 작업 횟수를 요구하는 Algorithm을 선택하는 것이 목표
• 알고리즘 비교를 위한 가정 환경
  • 할당된 Frame 수: 3개
    • Page Fault 발생 빈도는 Frame 개수와 반비례
  • Page 참조 순서(Reference String, 20번): {7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1}
  • 한번 참조된 Page는 교체되기 전까지 물리 메모리에 유지됨
    • 다시 참조할 때 물리 메모리에 Page가 존재하는 경우에는 Page Fault가 발생하지 않음

 

Optimal 알고리즘

• 앞으로 가장 오랫동안 사용되지 않을 Page부터 먼저 교체함
  • 모든 Algorithm 중 가장 낮은 Page Fault 발생 빈도를 가지는 이론상 최적의 Algorithm
  • 앞으로 어떤 Page가 사용될지 미래를 안다고 가정
    • 실제 구현 불가능

아무리 잘 해도 9번의 Page Fault 발생

 

FIFO 알고리즘

• 먼저 Frame이 할당된 Page를 먼저 교체함
  • 가장 단순한 알고리즘
• FIFO Queue를 이용해 구현 가능
• 멀티미디어 Data(동영상, 게임 등 data가 계속 들어오는 미디어)로 인해 주목 받음

 

SCR(Second Chance Replacement) 알고리즘

• FIFO 기법의 단점을 보완하는 기법
• 원리: 오랫동안 주 기억 장치에 존재하던 Page들 중에서 자주 사용되는 Page의 교체를 방지하기 위해 고안됨 
• 구현
  • FIFO Queue를 만들고 사용하되, 참조 Bit(Reference bit)를 두어 Page를 관리
  • 참조 Bit(Reference bit)
    • 최초로 Frame에 Load 될 때와 Page가 참조되었을 때마다 1로 Set
    • 일정 주기마다 다시 0으로 Reset 
  • 교체 대상 선정 과정
    • FIFO 순서에 따라 제거 대상으로 선택된 Page의 참조 Bit를 확인
    • 참조 Bit가 1인 경우, 최근에 사용된 Page이므로 제거하는 대신 참조 Bit만 0으로 reset하고, 다음 Page를 제거 대상으로 선택
    • 참조 Bit가 0인 경우, 오랫동안 사용되는 않는 Page이므로 제거(Victim)
• 변형 구조: 참조 비트 없이, Page Table Hit 발생 시 해당 Frame을 FIFO Queue의 맨 끝으로 옮기는 방식으로 구현하기도 함
  • LRU 알고리즘의 동작 방식에 가까움

 

Clock 알고리즘

• SCR 기법의 발전형
• Circular Queue를 사용하여 Frame을 관리
• 다음에 제거될 Page를 가리키는 Hand라는 Pointer를 둠
• Hand는 Queue를 따라 1칸씩 이동
• Hand가 가리키는 Page의 참조 bit가 1이라면, 최근에 접근한 Page이므로 제거하는 대신 참조 bit만 0으로 reset

 

LFU(Least Frequently Used) 알고리즘

• 사용 빈도가 가장 적은 Page를 교체하는 기법
• 지금까지 가장 적게 참조된 Page가 교체 대상으로 선택됨
• 문제점
  • 일단 Program 실행 초기에 많이 사용된 Page는, 그 후로 사용되지 않더라도 Frame을 계속 차지하는 문제가 있음

 

NRU(Not Recently Used) 알고리즘

• 최근에 사용하지 않은 Page를 교체하는 기법
• Page마다 참조 Bit와 변형 Bit를 두어 관리
  • 참조 Bit (Referenct bit)
    • 최초로 Frame에 Load 될 때와 Page가 참조 되었을 때마다 1로 Set
    • 일정 주기마다 다시 0으로 reset
  • 변형 Bit (Modified bit)
    • 최초로 Frame에 Load 될 때는 0
    • Page의 내용이 수정될 때 1로 Set
• Page 교체가 필요한 시점에 다음 순서대로 교체 대상으로 삼음

NRU

 

LRU(Least Recently Used) 알고리즘

• 가장 오랜 시간 참조되지 않은 Page부터 먼저 교체 (NRU보다 높은 정밀도)
  • Page 사용의 지역성(locality)을 고려하여, Optimal Algorithm과 유사하며 실제 구현 가능한 알고리즘
• 구현 방법
  • Counter의 사용: 참조된 시간을 기록
  • Queue의 사용: 한 번 사용한 Page를 Queue의 가장 위로 이동시킴
    • 가장 위의 Page: 가장 최근에 사용된 Page
    • 가장 아래의 Page: 가장 오래 전에 사용된 Page
• 가장 많이 사용되는 알고리즘으로 이기기 쉽지 않음

 

Swapping

• Page Out으로 메모리 부족을 해결하지 못할 경우 필요한 기법
• Swap Out 대상이 된 프로세스 전체를 Secondary Storage(Backing Storage)로 보냄
  • Swap 영역(Backing Store): Page Out이나 Swapping에 사용되는 Secondary Storage를 의미

• 물리 메모리 부족 시: 프로세스 0를 실행해야 하는데 공간이 부족할 경우, 프로세스 8 전체를 Swap Out하고, 그 자리에 9를 Load 할 수 있음
  • 실행 중인 메모리를 없애는게 아니라 속도는 좀 느리지만 용량이 큰 디스크를 보조 메모리 처럼 활용해서 현재 상태를 보존하며 저장하는 것

 

Contiguous Memory Allocation(연속 메모리 할당)

• 사용자 프로그램(User Program)이 물리 메모리의 연속된 영역을 사용하도록 하는 방식

Contiguous Memory Allocation 종류

 

1) Single Prtition Allocation(단일 파티션 할당)

• 가장 단순하게 메모리를 사용하는 방식
• User Program 영역을 한 번에 1개의 User Program만 사용하도록 함

 

2) Multiple Partition Allocation(다중 파티션 할당)

• Single Partition 방식에 Multiprogramming 개념을 추가
• User Program 영역을 여러 개의 User Program이 나누어 사용하도록 함 (동시에 여러 프로그램 실행 가능)

 

3) No Partition

• 각 Program이 필요에 따라 전체 user Program 영역을 사용
• 이 경우, Page/Swap Out 시에 Garbage Collection이 필요
  • 메모리가 빽빽하게 채워 넣어진 뒤, Swap Out으로 빈 공간이 생기면 그 공간을 Garbage Collection을 통해 압축(Compaction)하여 메모리 사이에 빈 공간이 없도록 메모리 정리/압축 한다는 뜻

 

Memory Allocation Problem(메모리 할당 문제)

• User Program이 Load 될 때, 물리 메모리의 OS 영역을 제외한 User 영역에 배치됨
  • 고려 사항: Protection, Relocation, 그리고 Swap 기법을 사용하며, 프로그램을 load할 때 메모리의 빈 공간 중 어디에 배치해야 효율적일지에 대한 고려가 필요
• 새로운 프로그램을 메모리의 빈 공간에 배치하는 방법은 크게 3가지가 있음

1. First-fit (최초 적합)

• 가장 먼저 발견한 곳에 배치
• 장점: 속도가 빠름

2. Best-fit (최적 적합)

• 사용 가능한 공간 중 가장 작은 곳에 배치
• 목표: 낭비되는 공간을 최소화
• 단점: 모든 사용 가능한 공간을 검색해야 하므로 속도가 느림

3. Worst-fit (최악 적합)

• 사용 가능한 공간 중 가장 큰 곳에 배치
• 목표: 남는 공간이 가장 커서, 다음에 들어올 큰 프로그램에게 유용하도록 함
  • Best-fit으로 작은 공간을 남기면 어차피 아무도 못 써. 차라리 왕창 남겨서 다른 program들이 쓸 수 있게 하자!
• 단점: Best-fit처럼 모든 공간을 검색해야 하며, 큰 공간이 작은 조각으로 빠르게 분해되어 비효율적일 수 있음

 

Fragmentation(단편화)

• 메모리가 할당되고 해제되는 과정에서 발생하는 비효율적인 메모리 사용 현상
• External Fragmentation(외부 단편화)
  • 정의: 프로그램에게 할당 후 남은 memory의 총 공간은 새로운 할당 요청에 충분하지만, 그 공간들이 연속적이지 않아 사용할 수 없는 경우
  • 해결책: Paging은 비연속적인 할당을 허용하여 External Fragmentation을 해결할 수 있음
• Internal Fragmentation(내부 단편화)
  • 정의: 할당된 메모의 크기가 요청된 메모리의 크기보다 조금 더 커서, 할당에는 성공했지만 그 차이만큼의 영역을 사용할 수 없는 경우
  • ex) Paging에서 Page Frame이 4KB로 고정되었는데, 요청한 물리 메모리 영역이 3998 byte인 경우, 98 byte의 Internal Fragmentation이 발생
  • Paging은 페이지 크기가 4KB로 고정되어 Internal Fragmentation을 해결할 수 없음
    • 해결법? 어쩔 수 없음 외부 단편화에 비하면 큰 문제가 아니니 감당해야 함

External Fragmentation 예시

• 최종적으로 남는 공간은 660K지만 할당될 수 있는 최대 프로세스 크기는 300K
  • Paging으로 해결 가능

 

Protection

• Contiguous Memory Allocation 방법을 사용할 때, OS의 메모리 영역과 User Program의 메모리 영역은 서로 구분되어야 함
• 서로의 영역을 침범하지 못하도록 보호를 해야 함
• 사용자 프로그램이 실수 or 악의적으로 OS 영역을 건드리면 시스템이 멈춤

 

Relocation

• User Program은 재배치 가능한 주소로 표현됨
• 재배치 가능한 주소를 이용하여 Program이 어느 위치에 Load 되더라도 쉽게 Code의 주소를 결정할 수 있어야 힘
• 프로그램은 항상 자기가 0번지부터 시작한다고 생각

 

Protection과 Relocation을 위한 Hardware의 지원

• CPU는 접근하려는 주소를 검사하고 변환하는 하드웨어 장치를 사용
• Limit Register와 Relocation Register를 이용하여 구현
• Limit Register(제한 레지스터)
  
  • 역할: 참조가 허용되는 논리 주소의 최댓값을 저장
    • Protection에서 프로그램이 OS에 접근하는 것을 막는 역할을 함
  • 작동: CPU가 발생시킨 논리 주소가 Limit Register 값보다 작은지 비교하여, 참조하는 주소가 해당 프로그램에게 허용되는 영역인지를 판별
    
    • Logical Address < Limit Register 인 경우에만 허용
• Relocation Register(재배치 레지스터)
  • 역할: Program이 차지하는 주소 영역 중 첫 번째 물리 주소(Base Address)를 저장
    • 프로그램의 논리 주소(0으로 생각 중)가 실제 메모리에서는 어디(ex. 1000번지)에서 시작하는지를 알려주는 기준점
  • 작동: CPU가 발생시킨 논리 주소에 Relocation Register 값을 더하여 실제 물리 메모리 주소(Physical Address)로 변환
    • Physical Address = Logical Address + Relocation Register

• 주소 변환 과정
  1. CPU가 논리 주소를 생성
  2. 이 논리 주소가 Limit Register보다 작은지 확인(Protection): 작지 않으면 오류(trap)
  3. 논리 주소에 Relocation Register 값을 더하여 물리 주소를 계산(Relocation)
  4. 물리 주소를 사용하여 메모리에 접근