[운영체제] #10. Memory Management (2)

목차

• Page Replacement
• Swapping
• Contiguous Memory Allocation
• Fragmentation

 

Page Replacement

• 도입 배경
  
  • 메모리 과다 할당 상태에서 더 이상 Free Frame이 없을 경우 발생.
    • Multi Programming System 에서 Memory 내에 위치한 User Process 의 수가 증가함에 따라 발생
    • 모든 User Process 가 사용하는 Page 수보다 물리 Memory 의 Frame 수가 적은 상황
  • 물리 메모리에 없는 Page를 참조할 때, Page Fault가 발생.
• 정의 : 물리 Memory 에 위치한 Page 를 Disk 에 저장하고, 요구된 Page 가 해당 Frame 을 할당 받도록 하는 방법 
• 동작 과정
  • Step 1: 디스크에서 요청된 Page의 위치를 찾음.
  • Step 2: 물리 메모리에 Free Frame이 있는지 확인.
    • Free Frame 있음: 바로 할당.
    • Free Frame 없음: Victim Frame 선정 및 교체.
  • Step 3: Victim Frame의 내용을 디스크로 저장.
  • Step 4: 디스크에서 요청된 Page를 메모리에 로드.
  • Step 5: Page Table 갱신 후 프로세스 재개.

• 고려 사항
  • Frame Allocation Algorithm: 각각의 User Process 에게 어떻게 Frame 을 분배해 줄 것인가?
  • Page Replacement Algorithm:
    • 교체할 Page(Victim Page)를 어떻게 선택할 것인가?
    • 효율적인 알고리즘 선택이 시스템 성능에 중요.
  • I/O 비용 최적화: Page 교체로 인해 발생하는 I/O 작업 비용을 줄이는 것이 중요.

 

Page Replacement Algorithms

• 목적
  • Page Fault 빈도를 낮추는 알고리즘 선택
• 예시
  • 세 개의 Frame 이 할당됨
    • Page Fault 발생 빈도는 Frame 의 개수와 반비례함
  • Page 를 참조하는 순서 - 20번
    • 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3,2, 1, 2, 0, 1, 7, 0, 1
  • 한번 참조된 Page 는 Page 교체가 일어나기 전에는 물리 Memory 에 위치한다.
    • 다시 참조할 때 물리 Memory 에 Page 가 존재하는 경우에는 Page Fault 가 발생하지 않음

 

1. Optimal Algorithm

• 원리:
  • 앞으로 가장 오랫동안 사용되지 않을 Page를 교체.
  • Page Fault 발생 최소화를 목표로 한 이상적인 알고리즘.
  • 하지만 실제로는 미래를 예측할 수 없기 때문에 구현이 불가능.
• 예시:
  • Reference String: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
  • Frame 수: 3
  • Page Fault 횟수: 9번

• 동작 과정
  • 뒤에 숫자들을 보면 7번이 가장 적게 사용됨
  • 3번째 이후에 7 -> 2로 바꿔줌

 

2. FIFO Algorithm

• 원리:
  • 가장 먼저 들어온 Page를 먼저 교체.
  • 간단한 구현이 가능하며 FIFO Queue를 사용.
• 특징:
  • 단점: Belady's Anomaly 발생 가능 (Frame 수가 증가해도 Page Fault가 증가할 수 있음).
• 예시:
  • Reference String: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
  • Frame 수: 3
  • Page Fault 횟수: 15번

• 동작 과정
  • 7번이 가장 먼저 들어왔다
  • 3번째 이후에 7 -> 2로 바뀐다.

 

3. SCR Algorithm (Second Chance Replacement)

• 원리:
  • FIFO를 기반으로 하되, 참조된 Page에 한 번 더 기회를 부여. (최근에 사용된 적이 있으면 기회줌)
  • 각 Page에 Reference Bit 추가:
    • Page가 참조될 때마다 Reference Bit을 1로 설정.
    • 일정 주기 마다 다시 0으로 Reset 
    • 교체 대상 Page의 Reference Bit이 1이라면, 초기화 후 다시 Queue 끝으로 이동.
• 예시
  • Page Reference String: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2
  • 프레임 수: 3 (큐는 최대 3개의 페이지를 저장)
  • 동작 과정
    • 페이지 7:
      • 큐: [7]
      • 참조 비트: [1] (페이지가 처음 들어오면 참조 비트 1로 설정)
    • 페이지 0:
      • 큐: [7, 0]
      • 참조 비트: [1, 1]
    • 페이지 1:
      • 큐: [7, 0, 1]
      • 참조 비트: [1, 1, 1]
    • 페이지 2 (페이지 교체 필요):
      • 큐 맨 앞 페이지 7 확인 → 참조 비트 1, Second Chance 부여.
      • 참조 비트를 0으로 설정하고 큐 뒤로 이동.
      • 다음 페이지 0 확인 → 참조 비트 1, Second Chance 부여.
      • 참조 비트를 0으로 설정하고 큐 뒤로 이동.
      • 다음 페이지 1 확인 → 참조 비트 1, Second Chance 부여.
      • 참조 비트를 0으로 설정하고 큐 뒤로 이동.
      • 모든 페이지에 Second Chance를 부여한 후, 다시 7로 돌아옴 → 참조 비트 0, 교체.
      • 큐: [2, 0, 1]
      • 참조 비트: [1, 0, 0]

 

4. Clock Algorithm

 

• 원리:
  • SCR (Second Chance Replacement)의 발전형.
  • Page를 원형 Queue로 관리하며, Hand라는 Pointer를 사용.
  • Hand가 가리키는 Page의 Reference Bit을 확인:
    • Reference Bit이 0이라면, 해당 Page를 교체.
    • Reference Bit이 1이라면, Reset(0) 후 Hand를 다음 Page로 이동.

• 예시
  • Page Reference String: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2
  • 프레임 수: 3 (원형 큐는 최대 3개의 페이지를 저장)
  • 초기 상태:
    • 큐: 비어 있음
    • 참조 비트: 모든 페이지 0
  • 동작 과정
    • 페이지 7:
      • 큐: [7]
      • 참조 비트: [1] (새 페이지는 참조 비트 1로 설정)
      • Hand: 페이지 7 가리킴.
    • 페이지 0:
      • 큐: [7, 0]
      • 참조 비트: [1, 1]
      • Hand: 페이지 0 가리킴.
    • 페이지 1:
      • 큐: [7, 0, 1]
      • 참조 비트: [1, 1, 1]
      • Hand: 페이지 1 가리킴.
    • 페이지 2 (페이지 교체 필요):
      • Hand가 가리키는 페이지 1 확인 → 참조 비트 1, Second Chance 부여 → 참조 비트 0으로 설정하고 다음으로 이동.
      • Hand가 페이지 7 확인 → 참조 비트 1, Second Chance 부여 → 참조 비트 0으로 설정하고 다음으로 이동.
      • Hand가 페이지 0 확인 → 참조 비트 1, Second Chance 부여 → 참조 비트 0으로 설정하고 다음으로 이동.
      • Hand가 다시 페이지 1로 돌아옴 → 참조 비트 0, 교체.
      • 큐: [7, 0, 2]
      • 참조 비트: [0, 0, 1]
      • Hand: 페이지 2 가리킴.
    • 페이지 0:
      • 페이지 0은 이미 존재.
      • 참조 비트: [1, 1, 0] (참조된 페이지는 참조 비트 1로 설정).
      • Hand : 페이지 2 가리킴 (변동X)

 

5. LFU Algorithm (Least Frequently Used)

• 원리
  • 가장 적게 참조된 Page를 교체.
  • 각 Page의 참조 횟수를 기록하고, 가장 작은 참조 횟수를 가진 Page를 선택.

• 예시
  • Page Reference String: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3
  • Frame 수: 3 (최대 3개의 Frame만 사용 가능)
  • 동작 과정
    • 7 삽입:
      • Page 7 삽입 (참조 횟수: 1).
      • Frame 상태: [7]
      • 참조 횟수: {7: 1}
    • 0 삽입:
      • Page 0 삽입 (참조 횟수: 1).
      • Frame 상태: [7, 0]
      • 참조 횟수: {7: 1, 0: 1}
    • 1 삽입:
      • Page 1 삽입 (참조 횟수: 1).
      • Frame 상태: [7, 0, 1]
      • 참조 횟수: {7: 1, 0: 1, 1: 1}
    • 2 삽입 (Page Fault):
      • Page 2 삽입. Frame이 가득 찼으므로 교체 발생.
      • 교체 대상: 모든 페이지 참조 횟수가 같음(1), FIFO 규칙 적용 → 7 제거.
      • Frame 상태: [2, 0, 1]
      • 참조 횟수: {2: 1, 0: 1, 1: 1}
    • 0 참조 (Hit):
      • Page 0 참조 (참조 횟수: 2).
      • Frame 상태: [2, 0, 1]
      • 참조 횟수: {2: 1, 0: 2, 1: 1}
    • 3 삽입 (Page Fault):
      • Page 3 삽입. 교체 발생.
      • 교체 대상: 참조 횟수가 가장 낮은 페이지 2와 1 중 멀리 있는 1 제거.
      • Frame 상태: [2, 0, 3]
      • 참조 횟수: {2: 1, 0: 2, 3: 1}
    • 0 참조 (Hit):
      • Page 0 참조 (참조 횟수: 3).
      • Frame 상태: [2, 0, 3]
      • 참조 횟수: {3: 1, 0: 3, 1: 1}
  • 문제점 : Program 이 실행 초기에 많이 사용된 Page 는, 그 이후로 사용되지 않더라도 Frame 을 계속 차지하는 문제

 

6. NRU Algorithm (Not Recently Used)

• 원리
  • 최근에 사용하지 않은 Page를 교체.
  • Reference Bit과 Modified Bit (변형 비트) 를 사용:
    • Reference Bit: Page 참조 여부.
    • Modified Bit: Page 안에 데이터 내용 변경 여부.
  • 참조와 변형이 같이 있으면 잘 빼지 않는다.
• 우선 순위
  • Class 0: Reference = 0, Modified = 0 (가장 우선적으로 교체)
  • Class 1: Reference = 0, Modified = 1
  • Class 2: Reference = 1, Modified = 0
  • Class 3: Reference = 1, Modified = 1 (가장 나중에 교체)
• 예시
  • Frame 크기: 3
  • Reference String: 7, 0, 1, 2, 0, 3, 0, 4, 2
  • 초기 Reference/Modified 비트: 모든 페이지의 Reference와 Modified 비트는 0으로 시작.
  • 동작 과정
    • 7 삽입 
      Frame: [7]
      Reference Bit: [1]
      Modified Bit: [0]
    • 0 삽입 
      Frame: [7, 0]
      Reference Bit: [1, 1]
      Modified Bit: [0, 0]
    • 1 삽입 
      Frame: [7, 0, 1]
      Reference Bit: [1, 1, 1]
      Modified Bit: [0, 0, 0]
    • 2 삽입 (Page Fault 발생)
      Frame이 가득 찼으므로 교체 필요.
      • 모든 페이지의 Reference Bit은 1이므로 Class 3에 속함.
      • Reference Bit을 0으로 초기화 (주기적 Reset).
      • 페이지 7 제거 
        Frame: [2, 0, 1]
        Reference Bit: [1, 1, 1]
        Modified Bit: [0, 0, 1]  // 만약 데이터 변경이 일어났으면
    • 0 참조 (Page Hit)
      Frame: [2, 0, 1]
      Reference Bit: [1, 2, 1] 
      Modified Bit: [0, 0, 1]
    • 3 삽입 (Page Fault 발생)
      Frame이 가득 찼으므로 교체 필요.
      
      • 페이지 2 제거.
        Frame: [3, 0, 1]
        Reference Bit: [1, 1, 1]
        Modified Bit: [0, 0, 1]

 

7. LRU Algorithm (Least Recently Used)

• 원리
  • 가장 오랫동안 사용되지 않은 Page를 교체 
  • Page 참조 시점을 기록하여 가장 오래된 Page를 Queue에서 제거.
• 특징
  • Optimal Algorthm 에 가장 가까운 성능 제공
  • 구현에 비교적 많은 Overhead (참조 시간 기록 및 정렬)
• 장점 : Locality 를 잘 활용하며, 적절한 성능 제공
• 단점 : Reference 시점 저장과 비교 연산의 비용 발생
• 구현
  • Counter 사용 : 참조된 시간 기록
  • Queue 사용 : 한번 사용한 Page 를 Queue 가장 위로 이동
    • 가장 위의 Page 는 가장 최근에 사용된 Page
    • 가장 아래의 Page 는 가장 오래 전에 사용된 Page
• 예시
  
  • Reference String: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
  • Frame Size: 3 (메모리 크기)
  • 초기 상태: Frame은 비어 있음.
  • Page Fault 발생 횟수 : 12번

 

 

 

Swapping

• 정의
  • Memory 부족 문제를 해결하기 위한 기법.
  • 프로세스 전체를 Secondary Storage (Backing Store)로 옮겨 메모리를 비우는 방식.
  • 사용된 메모리가 필요 없어지거나 다른 프로세스 실행을 위해 다시 불러오면 Swap In.
• 동작 과정
  • Swap Out: 특정 프로세스를 메모리에서 디스크로 이동.
  • Swap In: 디스크에 있던 프로세스를 메모리로 다시 복원.
• 용도 : Multi-programming 환경에서 동시에 실행 가능한 프로세스의 수를 늘리기 위해 사용.
• 단점 : Swap 영역으로의 이동과 복원이 빈번하면 I/O 비용 증가로 인해 성능 저하 발생.

 

 

Contiguous Memory Allocation

• 정의
  • 연속된 메모리 블록을 프로세스에 할당하는 방식.
  • 물리적으로 인접한 메모리 공간을 사용.
• 종류
  
  • Single Partition Allocation:
    • Program 하나를 Memory 에 올림
    • 단순하지만, 동시에 여러 프로세스를 실행할 수 없음.
  • Multiple Partition Allocation:
    • 메모리를 여러 개의 고정된 크기의 파티션으로 나눔.
    • 각각의 파티션에 프로세스를 할당하여 Multi-programming 지원.
  • No Partition:
    • 메모리를 프로세스 크기만큼 동적으로 할당.
    • 파편화 문제를 해결하기 위해 Garbage Collection 필요.

      

Memory Allocation Problem

• 정의
  • User Program이 Load될 때, 메모리의 OS 영역을 제외한 User 영역에 적절히 배치해야 하는 문제.
  • Protection, Relocation, Swap 등의 기법을 사용하여 적절한 메모리 관리 필요.
• 기법
  • First-fit:
    • 메모리의 빈 공간 중 첫 번째로 적합한 공간에 프로그램을 배치.
    • 장점: 탐색 시간 최소화.
    • 단점: External Fragmentation 발생 가능.
  • Best-fit:
    • 가장 적은 크기의 최적 공간에 프로그램을 배치.
    • 장점: 공간 낭비 최소화.
    • 단점: 탐색 시간이 오래 걸림.
  • Worst-fit:
    • 가장 큰 크기의 공간에 배치.
    • 장점: 큰 빈 공간을 유지하여 작은 프로그램 수용 가능.
    • 단점: Internal Fragmentation 발생 가능.

 

 

Fragmentation

• External Fragmentation:
  • 메모리의 사용 가능한 총 크기는 충분하지만, 연속된 공간이 없어 배치하지 못하는 경우.
  • 해결 방법 (Paging) : 메모리를 고정된 크기(Page)로 나누어 연속성 문제 해결.
• Internal Fragmentation:
  • 프로그램이 요청한 메모리보다 더 큰 고정 크기의 Frame/Page가 할당되어 낭비되는 경우. (피할 순 없음)
    ex) 3998 Bytes 요청 시, 4KB Frame이 할당되어 2 Bytes 낭비.

 

• 상황 (Externel Fragmentation)
  • 3번째 상황에서 $P_{5}$ 를 실행하고 싶지만, 연속적인 500 K 메모리 (300, 260 만 있음) 가 없어서, P1 을 죽이고 할당할 수 밖에없다.
• 결과:
  • 메모리 일부 공간이 External Fragmentation으로 사용되지 못함.
  • Page 기반 관리로는 Internal Fragmentation이 발생할 수 있음.

 

 

Protection 과 Relocation

• Protection:
  • User Program과 OS Memory 영역을 구분.
  • 잘못된 접근으로 인한 문제 방지.
• Relocation:
  • 프로그램이 메모리에 어디에 위치하든 주소 변환으로 접근 가능.
• Protection과 Relocation을 위한 Hardware의 지원
  • Limit Register와 Relocation Register를 이용하여 구현
    
    

• 개념
  • Limit Register: 참조가 허용되는 주소의 최대값.
  • Relocation Register: 프로그램이 실제 메모리 상에서 차지하는 주소 영역의 시작 주소.