[OS 8편] Virtual Memory

Virtual Memory는 총 7개의 하부 내용으로 구성됩니다.

 

1. 요구페이징

2. Page Fault

3. Page Replacement

4. Page Replacement Algorithm

5. Various Caching methods

6. Page Allocation

7. Thrashing

 

✔️ 요구페이징

• OS가 어떤 식으로 프로세스에게 메모리를 할당하는 가?
• 가상메모리
  • 자기 자신만의 메모리 공간.
  • 프로세스마다 0번지부터 주소 공간을 가지고, 일부는 메모리에 적재하기도 하고 나머지는 swap 영역에 존재하기도 함.

 

• 요구페이징
  • 프로그램 실행 시 프로세스를 구성하는 모든 페이지를 한꺼번에 메모리에 올리는 것이 아니라 당장 사용될 페이지만 올리기.
  • CPU 요청이 들어온 후에야 해당 메모리에 적재.
    
    
  • 장점
    • I/O 양의 감소.
    • memory 사용량 감소.
    • 빠른 응답 시간.
    • 더 많은 사용자 수용 가능.
  • InValid - Valid bit
    • 각 페이지가 메모리에 존재하는 지 확인.
    • Invalid 의 의미
      • 사용되지 않는 주소 영역의 경우.
      • 페이지가 물리적 메모리에 없는 경우.
    • 처음에는 모든 entry가 invalid.
    • address translation 시에 invalid로 되어 있으면, page fault!

 

✔️ Page Fault

• Invalid reference? -> abort process.
• get an empty frame( 없으면 뺏어오기, replace)
• 해당 페이지를 disk에서 메모리로 읽어오기.
  • Disk I/O가 끝나기 전까지 해당 프로세스는 CPU를 선점당함. (block 상태)
  • Disk read가 끝나면 page table에 엔트리 작성, valid 처리.
  • ready queue에 프로세스 세우기, dispatch later.

 

✔️ Page Replacement

• 어떤 프레임을 빼앗아 올지 결정하는 알고리즘.
• 곧바로 사용되지 않는 page를 쫓아내는 것이 좋다.
• 동일한 페이지가 여러 번 쫓겨났다가 다시 들어올 수도 있음.
• OS의 업무이다.
  
  
• Replacement Algorithm
  • page fault rate을 줄이는 것이 목표.
  • 알고리즘 평가.
    • 주어진 page reference string에 대해 page fault가 얼마나 발생하는 지 조사.
  • 변경된 부분이 있다면, 변경된 부분을 반영하여 Backing Store에 저장.
• Global Replacement VS Local Replacement
  • Global Replacement
    • Replace 시 다른 프로세스에게 할당된 프레임을 빼앗아 올 수 있음.
    • 프로세스 별 할당량을 조절하는 또 다른 방법.
    • FIFO, LRU, LFU등의 알고리즘을 global replacement로 사용 시 해당.
    • working set, pff 알고리즘 사용.
  • Local Replacement
    • 자신에게 할당된 페이지 프레임 내에서만 replacement.
    • FIFO, LRU, LFU등의 알고리즘을 프로세스 독자별로 이용 시 해당.

 

✔️ Page Replacement Algorithm

• Optimal Algorithm
  • 미래에 참조되는 페이지를 알고 있다고 가정.
  • 실제 시스템에서는 활용할 수 없음.
  • 가장 먼 미래에 참조되는 페이지 교체.
  • 다른 알고리즘에 성능 척도(upperbound)를 제공하는 정도의 용도.
• FIFO Algorithm
  • 들어온 순서대로 내보내기.
  • 메모리가 증가했는데도, page fault rate이 증가하는 이상 현상 발생. (FIFO Anomaly)
• LRU(Least Recently Used) Algorithm
  • 제일 오랫동안 참조되지 않은 페이지를 내보낸다.
  • 시간지역성: 최근 참조된 페이지가 가까운 미래에 다시 참조될 가능성이 높은 성질.
  • 과거를 통해 내보낼 page 결정.
  • page fault 감소.
  • 뒤에서부터 reference string 확인하기.
  • 연결 리스트 형태 -> O(1)
• LFU(Least Frequently Used) Algorithm
  • 참조횟수가 가장 적은 페이지 교체.
  • 참조 횟수가 최저인 페이지가 여러 개면, LFU 알고리즘에서 자체적으로 page 선택.
    • 성능 향상을 위해 가장 오래 전에 참조된 페이지를 지우도록 구현하기도 함.
  • 장단점
    • LRU처럼 직전 참조 시점만 보는 것이 아닌 장기적인 시간의 규모를 보기 때문에 page의 인기도를 좀 더 정확하게 반영 가능.
    • 참조 시점에 최근성이 반영되지 않음.
    • LRU보다 구현이 복잡.
  • 참조 횟수 카운트 하기.
  • 힙 구조 -> O(logN)
• Clock Algorithm(=Not Used Recently <NUR>)
  • LRU의 근사 알고리즘.
  • 여러 명칭으로 불림
    • Second Chance Algorithm
    • NUR(Not Used Recently), NRU(Not Recently Used)
  • LFU, LRU는 SW적으로 기억할 것이 많아 오버헤드가 크다.
  • Clock 알고리즘은 HW적인 지원을 받음.
  • 동작 원리
    • 프레임 당 reference bit를 사용해 교체할 페이지 결정. (circular list)
    • 프레임 내 페이지가 참조되면 자동으로 reference bit가 1로 세팅.
    • reference bit가 1인 것은 0으로 바꾸며 이동.
    • 이동 중에 0인 것을 찾으면 해당 페이지 교체.
    • 한 바퀴를 돌고 이전에 1이었던 것이 아직도 0이라면 그때 replace 됨.
    • 자주 참조되는 페이지 였다면, 시곗바늘이 0으로 바꾸고 갔더라도 한바퀴 돈 다음에 다시 그 자리에 왔을 때, 1로 세팅이 되어있었을 것.
    • 적어도 시곗바늘이 한바퀴 도는데 소요되는 시간만큼 메모리에 유지시켜둠으로서 페이지 부재율을 줄이도록 설계 되어 있기 때문에 2차 기회 알고리즘이라고도 함.
  • reference bit는 HW에 의해 세팅.
  • OS는 어떤 페이지를 out 시킬 지 결정.

 

✔️ Various Caching Method

• 캐싱 기법
  • 한정된 공간(=캐시)에 요청된 데이터를 저장해두었다가 후속 요청 시 캐시로부터 직접 서비스 하는 방식
  • Paging 시스템 외에옫 buffer caching, cache memory, web caching 등 다양한 분야에서 사용.
  • CPU와 RAM 사이에 캐시 메모리 존재.
• 캐시 운영의 시간 제약
  • 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우, 실제 시스템에서 사용 불가.
  • Buffer Caching or Web Caching의 경우, O(1) 혹은 O(logN)의 시간.
  • Page System의 경우
    • page fault인 경우 OS가 관려.
    • 페이지가 이미 메모리에 존재하는 경우, 참조 시각등을 OS가 알 수 없음.
    • O(1)인 LRU 리스트 조차 조작 불가.
  • 주소변환에서 메모리 참조까지 OS가 하는 일은 없음. 다만 trap 발생(메모리에 없을 때 = page fault)
  • OS는 가장 오래된 페이지를 알고 있는가? 메모리에 page가 없는 경우에만 알 수 있음.
  • LRU, LFU는 페이징 시스템에서 불가능. 다만, 웹 캐싱이나 버퍼케싱에서는 가능.

✔️ Page Allocation

• 각 프로세스마다 얼마의 frame을 할당할 것인가?
• Allocation의 필요성.
  • 메모리 참조 명령 수행 시, 명령어, 데이터 등 여러 페이지 참조.
    • 명령어 수행을 위해서 최소한 할당되어야 하는 frame 수 존재.
  • Loop를 구성하는 page는 한꺼번에 allocate 되는 것이 유리함.
    • 최소한의 allocation이 없으면, 매 loop마다 page fault 발생.
• Allocation Scheme
  • Equal Allocation: 모든 프로세스에 똑같은 수의 프레임 할당.
  • Propotional Allocation: 프로세스 크기에 따른 프레임 할당.
  • Priority Allocation: 프로세스 우선순위에 따른 프레임 할당.
    
    

✔️ Thrashing

• 프로세스의 원활한 수행을 위해 필요한 최소한의 페이지 프레임 수를 할당받지 못하면 page fault rate이 높아진다.
• 위 같은 상황이 벌어지면, CPU 이용률이 줄어들게 되고 OS는 이를 해결하기 위해 MPD(Multi Programming Degree)를 높여야 한다고 판단.
• 그러면 또 다른 프로세스가 시스템에 추가되고, 프로세스별 프레임 할당 수가 적어짐.
• 프로세스는 swap in/out으로 매우 바쁘고, CPU는 한가해지는 현상이 Thrashing이다.
  
  
• 그러므로 MPD를 적절히 조절해 CPU 이용률을 높이며, thrashing을 방지하기 위한 알고리즘이 등장.
  • 1. Working Set Algorithm
  • 2. PFF(Page Fault Frequency) Algorithm
    
    
• 1. Working Set Algorithm
  • Locality of Service
    • 프로세스는 특정 시간동안 일정 장소를 집중적으로 참조하는 경향.
    • 집중적으로 참조하는 page의 모임을 locality set이라 함.
  • Working Set Model
    • locality에 기반하여 프로세스가 일정시간 동안 원활하게 수행되기 위해서는 한꺼번에 메모리에 올라와 있어야 하느 페이지의 집합을 working set이라 함.
    • working set 모델에서 process의 working set 전체가 메모리에 올라와 있어야 하고 그렇지 않은 경우 모든 프레임을 반납한 뒤에 swap out됨.
    • 스래싱 방지.
    • MPD 결정.
  • Working Set Algorithm
    • 메모리에 한꺼번에 올라갈 프레임을 정하기 위해 working set window 사용.
    • working set에 속한 페이지는 메모리에 유지하고 아닌 것은 버림.
      • 즉, 참조된 후 윈도우 크기 만큼의 시간동안 메모리에 해당 페이지 유지한 뒤 버림.
    • working set의 크기는 동적으로 변경됨.
• 2. PFF(Page Fault Frequencey) Algorithm
  • 프로세스의 page fault rate을 주기적으로 조사하고 이 값에 근거해 각 프로세스에 할당할 메모리 양을 동적으로 조사.
  • Page fault rate에 상한과 하한을 둔다.
    • 상한을 넘으면, frame을 더 할당.
    • 하한을 넘으면, frame을 뺏기.
  • 빈 프레임이 없다면, 프로세스 스왑아웃하기.
  • 프로세스마다 일정의 page fault rate을 유지하기.