[운영체제] 8. Virtual Memory (2)

키워드

clock algorithm, allocation scheme, global replacement, thrashing, working-set, PFF

 

Paging System에서 LRU, LFU 가능한가?

• 프로세스 A에서 page fault trap 발생 시 디스크 접근(I/O)이 필요로 하기 때문에
  CPU 제어권이 운영체제로 넘어감
• 운영체제가 디스크에 있는 page fault가 난 page를 읽어서 물리적인 메모리로 올려놔야 되는데
  물리적인 메모리에서 뭔가를 쫓아내야 하는데 
• 가장 오래전에 참조된 page를 쫓아내야 되는데(LRU) 가장 오래된 걸 운영체제는 알 수 없고
• 가장 참조 횟수가 적은 page를 쫓아내야 되는데(LFU) 가장 참조 횟수가 적은 걸 마찬가지로 운영체제는 알 수 없다.
• 프로세스가 요청한 page가 이미 메모리에 올라와 있는 경우에는 운영체제가 CPU한테 안넘어가고 
  하드웨어적으로 주소 변환을 하여 CPU로 읽어들이기 때문에 접근 관련 정보(시간 등)를 운영체제는 알 수 없다.
• 반면, CPU 제어권이 운영체제한테 넘어오면 디스크에 있는 page가 메모리에 올라오는 시간을 알 수 있다.
  -> 운영체제한테 주어지는 정보가 반쪽만 주어짐
  
  
• LRU, LFU 작업은 CPU를 얻은 운영체제가 인스트럭션 하나하나를 통해서 할 수 있는 일인데 
  메모리에 이미 있는 page에 대해서는 운영체제한테 CPU가 넘어오지 않기 때문에
  운영체제는 어떤 page가 가장 최근에 참조됐는지, 어떤 page의 참조 횟수가 많은지를 알 수 없기 때문에
  LRU, LFU 같은 알고리즘을 Paging System. 즉, Virtual Memory System에서 사용할 수 없다.
  -> Buffer caching, Web caching에서 사용될 수는 있음
• => 대신 Clock Algorithm을 사용

 

Clock Algorithm

• LRU의 근사(approximation) 알고리즘
• 여러 명칭으로 불린다.
  • Second Chance Algorithm
  • NUR(Not Used Recently) or NRU(Not Recently Used)
• reference bit을 사용해서 교체 대상 페이지 선정(circular list)
  • reference bit = 1 : 최근 참조된 페이지
  • 하드웨어가 해주는 일
• 쫓아낼 page를 선별할 때 reference bit가 1인 경우 0으로 바꾸면서 넘어감
  0일 경우 교체 대상 page로 선별
  • 한 바퀴 돌아와서도(=second chance) 0이면 그 때는 replace
  • 자주 사용되는 페이지라면 second chance가 올 때 1
• Virtual Memory에서 일반적으로 사용하는 알고리즘

Clock Algorithm의 개선

• reference bit과 modified bit(dirty bit)을 함께 사용
• reference bit = 1
  -> 최근에 참조된 페이지
• modified bit = 1
  -> 최근에 변경된 페이지(I/O를 동반하는 페이지)

 

Page Frame의 Allocation

• 이전에 LRU, LFU, Clock Algorithm에서는 프로그램 여러 개가 물리적인 메모리에 올라가 있는 상태에서
  쫓아낼 때 어떤 프로세스에 속한 page인지에 무관하게 조건에 맞는 page를 쫓아냈다.
• Allocation problem: 각 process에 얼마만큼의 page frame을 할당할 것인가?
• Allocation의 필요성
  • 메모리 참조 명령어 수행 시 명령어, 데이터 등 여러 페이지 동시 참조
    -> 명령어 수행을 위해 최소한 할당되어야 하는 frame의 수가 있음
  • Loop를 구성하는 page들은 한꺼번에 allocate 되는 것이 유리
    -> 최소한의 allocation이 없으면 매 loop 마다 page fault

Allocation Scheme

• Equal Allocation: 모든 프로세스에 똑같은 개수 할당
• Proportional Allocation: 프로세스 크기에 비례하여 할당
• Priority Allocation: 프로세스의 priority에 따라 다르게 할당

 

Global vs. Local Replacement

Global Replacement

• Replace 시 다른 process에 할당된 frame을 빼앗아 올 수 있음
• Process 별 할당량을 조절하는 또 다른 방법
• FIFO, LRU, LFU 등의 알고리즘을 global replacement로 사용 시에 해당
• Working set, PFF 알고리즘 사용(할당에 효과가 있는 알고리즘들)
• 다른 프로그램의 page도 쫓아낼 수 있는 방법
• 쉽게 말해서 그때그때 경쟁해서 많이 가지거나 적게 가지거나 하는 방법이다.

Local Replacement

• 자신에게 할당된 frame 내에서만 replacement
• FIFO, LRU, LFU 등의 알고리즘을 process 별로 운영 시
• 프로그램한테 할당 후 새로운 page를 올려놓기 위해 쫓아낼 때 자신한테 할당된 page를 쫓아냄
• 쉽게 말해서 자기 몫을 미리 나눠준 후 알아서 쓰게 하는 방법이다.

 

Thrashing

• 어떤 프로그램한테 최소 메모리도 할당이 안됐을 때 page fault가 전체 시스템에서 아주 빈번히 발생하는 상황을
  Thrashing이라고 부른다.
• 프로세스의 원활한 수행에 필요한 최소한의 page frame 수를 할당 받지 못한 경우 발생
  
  
• page fault rate이 매우 높아짐
• CPU utilization이 낮아짐
• OS는 MPD(Multiprogramming degree)를 높여야 한다고 판단
• 또 다른 프로세스가 시스템에 추가됨(higher MPD)
• 프로세스 당 할당된 frame의 수가 더욱 감소
• 프로세스는 page의 swap in / swap out으로 매우 바쁨
• 대부분의 시간에 CPU는 한가함
• low throughput
• -> 위에 대한 상황이 그림으로 나와있듯, MPD가 너무 높아지게 되면 CPU utilization이 뚝 떨어져서
  시스템이 굉장히 비효율적이됨
• 이 경우 MPD를 조절해줘야 하는데, 동시에 메모리에 올라가있는 프로세스의 개수를 조절해줌으로서
  프로그램이 어느정도 메모리 확보를 할 수 있게 해줘야 한다.
  -> Working-Set algorithm, PFF algorithm

 

Working-Set Model

Locality of reference

• 프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조하는 특징을 가짐
• 집중적으로 참조되는 해당 page들의 집합을 locality set이라 함

Working-Set Model

• Locality에 기반하여 프로세스가 일정 시간 동안 원활하게 수행되기 위해
  한꺼번에 메모리에 올라와 있어야 하는 page들의 집합을 Working Set이라 정의함
• Working Set 모델에서는 process의 working set 전체가 메모리에 올라와 있어야 수행되고
  그렇지 않을 경우 모든 frame을 반납한 후 swap out(suspend)
• 이렇듯, working-set이 한꺼번에 메모리에 올라가는게 보장이 안될 경우 해당 프로세스의 메모리를 통째로 빼앗아
  Thrashing을 방지하고 MPD를 조절(결정)한다.

 

Working-Set Algorithm

• working-set을 미리 알 수는 없음
• 과거를 통해 추정
• 과거 x시간 동안 참조된 page들을 working-set이라고 간주해서 쫓아내지 않고 유지
  여기서의 x시간을 working set window라고 부른다.
• working set에 속한 page는 메모리에 유지, 속하지 않은 것은 버림
  즉, 참조된 후 x시간 동안 해당 page를 메모리에 유지한 후 버림
  
  
• process들의 working set size 합이 page frame의 수보다 큰 경우
  일부 process를 swap out 시켜 남은 process의 working set을 우선적으로 충족시켜준다.(MPD를 줄임)
• working set을 다 할당하고도 page frame이 남는 경우
  swap out 되었던 프로세스에게 working set을 할당(MPD를 키움)
  
  
• working set을 제대로 탐지하기 위해서는 window size를 잘 결정해야 함
• x 값이 너무 작으면 locality set을 모두 수용하지 못할 우려
• x 값이 크면 여러 규모의 locality set 수용
• x 값이 무한대면 전체 프로그램을 구성하는 page를 working set으로 간주

 

PFF(Page-Fault Frequency) Scheme

• page-fault rate의 상한값과 하한값을 둔다.
  • page-fault rate이 상한값을 넘으면 frame을 더 할당
  • page-fault rate이 하한값 이하면 할당 frame 수를 줄임
• 빈 frame이 없으면 일부 프로세스를 swap out

 

Page Size의 결정

page size에 대한 파급 효과

Page size 감소 시

• 페이지 수 증가
• 페이지 테이블 크기 증가
• Internal fragmentation 감소(사용 안되는 부분)
• Disk transfer의 효율성 감소
  -> Seek/rotation vs. transfer
• 필요한 정보만 메모리에 올라와 메모리 이용이 효율적
  -> Locality의 활용 측면에서는 좋지 않음
  
  
• 최근에는 page size를 점점 키우는 추세