[Operating System Concepts] Chapter10 Virtual Memory

운룡체제

 

1. Virtual Memory
2. Demand Paging
3. Copy-on-Write
4. Page Replacement
   • FIFO Page Replacement
   • Optimal Page Replacement
   • LRU Page Replacement
5. Thrashing

---

Virtual Memory

실제의 물리적인 메모리보다 더 메모리를 크게 사용할 수 있도록 하는 것을 의미한다.

 

• 메모리 구조를 무한의 가상 메모리라고 생각하고, 물리적인 메모리 에다가 필요할 때마다 매핑시킨다.
• 이러한 메모리에 로드 되어있는 가상 메모리는 HDD / SDD  등의 'backing store' 으로 간다.
• Contiguous Memory 에 가상 메모리를 작성한다고 하면 관리가 더 편리해질 것이다.

• 'shared memory' 처럼 공유되는 메모리가 필요하다고 할 때 접근이 편해진다. 페이지를 공유함으로서 가능해지는 부분이다.

Demand Paging

• Secondary storage(HDD, SDD의 Backing Store) 을 메인 메모리 공간으로 로딩하는 작업을 해주어야 한다.
• 한꺼번에 로딩하는건 (contiguous memory allocation)인데 현대적인 시스템은 안쓴다.
• 페이지 단위로 잘라서 올리기 (요청이 올 때만) → 근데, 필요할 때 페이지 로딩하는것은 다음과 같은 문제가 있다.
• Demand Page 가상 메모리는 어떻게 관리할 것인가? (=실행중에, 로딩하는 페이지를 어떻게 관리할 것인가?)

• 프로세스가 실행중일 때, 페이지가 메모리에 있다고 가정해야하고, 어떤 때에 'backing store'에 있는지를 표시해주어야 한다.
  (이를 하드웨어에서 지원해주어야 함)
• if valid → legal && in memory (유효하고 메모리 내부에 존재할때)
• if invalid → segfault || secondary stortage (backing store 에 존재할 때 / dirty bit 를 사용해서 구분해도 됨)

#Page Fault handling procedure

• 메모리에 로딩이 되지않고 page fault가 일어났을 때, 어떻게 처리해줄 것인가
  1. 유효성 검증(check validity)
  2. 만약 page fault 발생한다면 → page-in, swapping 으로 해결한다
  3. 메모리 영역에서 free frame을 찾아서 하드디스크의 영역에서 페이지영역을 로드하면 page-in이 된다.
  4. secondary page에서 읽고 새로운 프레임에 할당해 준다.
  5. 내부 테이블(internal table) 또는 페이지 테이블을 로드했다면 invalid 비트에서 → valid 비트로 변경
  6. instruction을 다시 실행한다.

steps in handling a page fault

1 : invalid (page fault 발생)

2 : trap 발생

3,4 : backing store에서 페이지를 가지고 free frame 을 로드함

5 : 페이지를 valid로 처리함

 

#Pure Demand Paging

• 요청할 때만 페이지를 메모리로 가지고 오는것을 의미한다.
• 하드디스크가 페이지로 구성되고 로딩 없이 필요할 때만 페이징을 한다.
• 성능이 나쁘다.

#Locality of Reference (참조 국부성)

• 항상 새로운 페이지를 참조하지 않는다.
• 하나의 instruction 에서는 다수의 page fault가 생길까? → 다행히도, 실행 프로세스는 이런 경우가 적다.
• 메모리 엑세스의 관점에서 메모리의 국부성을 가지기 때문에, 나쁘지 않은 성능을 보여줌

#Hardware Support to Demand Paging

• 페이지 테이블을 어떻게 관리할 것인가
• HDD등 Secondary memory(swap space)를 관리해야한다.
• SSD가 빠른이유? → 페이징 스왑이 지속적으로 일어나기 때문이다.

 

• page fault가 일어났을때, 맨처음 OS에서 트랩을 건다.→ cpu 점유하고 있던 P_0를 wait queue에 보내버린다.
• 프로세스 별로 페이지 테이블을 잘 관리해야한다.
• page fault가 발생할 경우 다시 insturction 불러오는 과정을 해야해서, 다시 시작할 수 있도록 한다.
• fetching 할 때 instruction을 다시 가져와서 오퍼런드를 다시 fetch시켜야 한다.

 

#Free Frame List

• 대부분의 OS는 페이지 오류를 처리할 때 사용할 수 있는 여유 프레임 풀, 여유 프레임 목록(free frame list)을 유지한다.
• 일반적으로 OS는 프레임을 다시 할당하기 전에 프레임의 이전 내용을 0으로 덮어쓴다. 이렇게 하면 프레임의 이전 사용자의 개인정보가 보호된다.
• page fault가 발생했을 때, 페이지가 저장소의 메모리로 swap in 시켜줄때면 free frame을 알아야한다.

 

#Performance of Demand Paging

• TLB(TLBR)와 거의 동일하다.
• ma (memory-access), p(page fault) 라고 할 때 아래와 같은 공식이 성립한다.
  • EAT = (1 - p) * ma + p * (page fault time)
• memory accesss < page * page fault time
• page fault 처리하는데 걸리는 시간
  • interrupt 걸리는 시간 (trap 거는 시간)
  • page read 하는 시간 (대부분의 시간을 여기서 차지함)
  • process Restart (미미함)

 

Copy-On-Write

Before / After, P1 modifies page C

 

• 모든 부모의 프로세스를 복사하기보다. 실제로 부모/자식 프로세스에서 사용하는 페이지만 복사하는걸 의미한다.
• 프로세스가 공유 페이지에 쓸 때만 공유 페이지를 복사한다. 전역변수가 저장되어있는 페이지영역만 분리시키면 된다.
• fork, exec 하는것과 동일하다고 보면 된다.

 

Page Replacement

Page Replacement 를 사용해야하는 3가지 이유

1. free frame 이 없는 경우는 어떻게 할 것 인가?
2. physical memory를 전부 다 사용해 버리는 경우?
3. 버퍼를 사용하는데 메모리 버퍼가 매우 크면?

 

B → swap in 하려고하는데 빈자리가 없음 → 페이지를 하나 희생시켜야함 → page replacement

• 비워줘야 하는 페이지를 어떻게 선정할 것인가? → '희생양' 선택 알고리즘을 사용하여 page replace 한다.
• 모두 실행되었다면 재 진입 할 수 있도록 한다.

Demand Paging 할 때 두가지 문제점이 존재한다.

 

• Frame-allocation algo. : 각 프로세스에 얼마나 많은 프레임이 할당되어야 하는가?
• Page-replacement algo. : 변경되어야 할 희생양을 선정을 어떻게 할 것인가?

→ demand paging의 효율이 조금이라도 높아지면 전체적인 I/O 시간이 줄어들기 때문에 최적화는 매우 중요하다.

 

 

#Page-replacement algo.

• page replacement algorithmns 의 평가기준 : page fault 의 비율을 낮춰야 한다.
• 당연하게도, 페이지 프레임 갯수가 많아질 수록 페이지 폴트가 적어진다. (그러나 항상 제한되어있다.)

frames 갯수에 따른 page fault수

 

 

#FIFO Page Replacement

 

• 가장 오래된 페이지를 희생양으로 설정하는 심플한 방법이다.
• 그러나 'Belady's Anomaly' 라는 문제가 발생한다.
  • page-fault rate 가 프레임이 증가할 수록 낮아져야하는데
  • frame 4 일때 이상현상이 발견됨

 

#Optimal Page Replacement

 

• 페이지 폴트가 적은 경우는 belady’s anomaly를 경험하지 않을것이다.
• 가장 쓸일이 없을 것 처럼 보이는 값을 버리는 방법을 채택하면 해결 될 것이다.
• 대신 구현하기 위해서는 미래의 지식이 있어야한다. → 얼마나 OPT에 근접하는지 체크하는 용도이다.

 

• 미래의 CPU burst를 알고있으면 최적을 알 수 있는데, 모르기 때문에 과거를 바라보고 구현해야 한다.
• FIFO는 과거 지향적, OPT는 (CPU 스케쥴러의 SJF 처럼) 미래 지향적이다.
• '아주 오랜시간동안 사용하지 않은 자원은 앞으로도 사용하지 않지 않을까?' 라는 가정으로 접근해야한다.

 

#LRU (Least Recently Used)

• 마지막으로 사용된 시간 기록이 가장 긴 페이지를 대체하는 방법이다.
• 한번 사용한 페이지는 빈번하게 사용할 가능성이 높다. (program locality)

 

• LRU가 위에서 소개한 페이지 교체 알고리즘 중 가장 성능이 좋다.
• 그러나, frame이 언제 마지막으로 사용 되었는지의 정보를 알아야한다.
• 오래된 프레임인지 판단을 위한 자료구조가 엄청나게 복잡해지고 개선하는데 오래걸린다. 하드웨어 지원도 받아야하는 부분이라 어려움이 가중된다.

• 가장 오래된 페이지를 가지고있는 것은, 가장 오래전에 참조한 것으로 판단할 수 있기 때문에 'Counter' 또는 'Stack' 사용
• reference bit를 제공해서 페이지에 dirty bit를 둠으로 써, 페이지 참조 할 때마다 '1' 으로 초기화 시켜준다.

 

#Second chance algo.

• FIFO replacement 알고리즘을 사용하지만 value 0이면 교체하고, 1이면 0으로 바꾸고 다시 선정하게 된다면 '희생자' 선정하자
• FIFO 를 이용하는데 추가로 ref. bit를 이용해서 second chance 를 준다. (LRU - approximation : lru를 흉내내는 것이다.)

 

Thrashing

• 프로그램이 실행하기에 충분한 pages 를 가지지 못할 때 page-fault rate 가 높아진다. (the degree of multi-programming)
  
  • 동시로 실행되는 스레드가 많아지면 많아질 수록 cpu사용량이 많아짐
    → cpu burst가 높아지다가 갑자기 떨어짐 (Thrashing)
• page frame이 100개인데 공평하게 줘도 1개씩밖에 못줌 → 계속 page fault 생길 수 있다.
• Thrashing 이 생기면, cpu는 일하는데 프로그램은 일을 안하게 되버린다.

Working-set model

• locality of reference 패턴을 보면 특정 페이지를 집중적으로 사용한다. 특히, 인접해있는 페이지들을 계속 같이 사용한다.
• 슬라이딩 윈도우 내부에 들어오는 페이지를 swap-in 시켜놓고 해당 윈도우를 관리하는 방식을 채택하는게 효율적이다.
• working set들이 최근에 사용한 페이지 참조이기 때문에, Active use인 상태이면 working set안에 있고 아니라면, 바깥에 있을것이기 때문에 희생양 으로 설정함