[OS Chapter 9] Virtual Memory

Demand Paging

: 실제로 필요할 때 page를 메모리에 올리는것(= 요청이 있으면 page를 메모리에 올리는 것)

• I/O양의 감소
• Memory 사용량 감소
• 빠른 응답 시간
• 더 많은 사용자 수용

 

Vaild / Invalid bit의 사용

출처: 강의

• invalid
  • 사용되지 않는 주소 영역 = 위의 그림에서 G, H
  • 페이지가 물리적 메모리에 없는 경우 = 위의 그림에서 B, D,E 
• address translation시 invalid면 page fault가 난다.

---

Page Fault

: invalid page를 접근하면 MMU가 trap을 발생 시킴(page fault trap)

 

kernel mode로 들어가서 page fault handler가 invoke된다.

 

 

출처: http://faculty.salina.k-state.edu/tim/ossg/Memory/virt_mem/page_fault.html

 

순서

1. 비정상적인 접근인지 확인(잘못된 주소, 권한) -> abort process
2. 빈 페이지 frame을 얻어온다. 없으면 뺏어온다.(replace)
3. 디스크에서 메모리로 읽어온다.
   • disk i/o가 끝나기전까지 cpu는 block당함
   • disk read가 끝나면 page tables entry 기록 vaild 설정
   • ready queue에 process를 insert
4. 프로세스가 CPU를 다시 잡고 running
5. 중단되었던 instruction부터 재시작

Perfomance of Deman Paging

page fault rate

0 = no page fault

1 = page faulkt

 

Access time =

(1 - p) x memory access +

p(OS & HW page fault overhead + [swap page out if needed] + swap page in + OS & HW restart overhead

 

page fault에 대한 오버헤드가 엄청 크게든다.

---

Page replacement

목표: page fault rate이 최대한 낮게 해야한다.

• 어떤 frame을 빼앗아 올지 결정
• 곧바로 사용되지 않을 page를 쫓아내야 함

출처: https://woodforest.tistory.com/14

 

 

알고리즘

1. optimal algorithm(= MIN, OPT)

미래에 대해서 미리 안다고 가정함. offline algorithm이다.

출처: https://woodforest.tistory.com/14

• 가장 먼 미래에 참조되는 page를 replace
• 예시에서는 5번의 page fault 이게 최적의 알고리즘
• upper_bound로서 참고로 사용됨

2. FIFO Algorithm

 

출처: https://woodforest.tistory.com/14

• 먼저 들어온 것을 먼저 내쫓음
• 새롭게 페이지안에 값을 넣을 때 page fault가 발생한다
• FIFO Anomaly -> frame을 더 늘려줬음에도 불구하고 page fault가 나는 현상

3. LRU(Least Rencently Used) Algorithm

출처: https://woodforest.tistory.com/14

• 가장 오래 전에 참조된 것을 지움
• 2/0/1 -> 2/0/3에서 1이 제일 오래전에 참조되었기 때문이다.

 

4. LFU(Least Frequently Used) Algorithm

: 참조 횟수(reference count)가 가장 적은 페이지를 지움

 

LRU와 LFU의 장단점

출처: 강의

• LRU는 1번 LFU는 4번을 replacement

출처: 강의

• LRU는 링크드 리스트로 구현해서 참조될때 가장 끝으로 보내면 된다. O(1) 비교가 필요 없음
• LFU는 다음 노드들과 참조횟수 비교를 하며 끝까지 비교하면서 간다. O(n)인데 heap을 사용하여 O(log n)의 시간복잡도를 가진다.

---

다양항 캐싱 환경

캐싱 기법

• 한정된 빠른 공간(= 캐시)에 요청된 데이터를 저장해 두었다가 후속 요청시 캐시로부터 직접 서비스하는 방식
• paging system외에도 cache memory buffer caching web caching 등 다양한 분야에서 사용

시간 제약

• 캐시 교체 알고리즘에 대한 시간의 제약이 있음
• O(log n) 까지 허용
• page system의 경우 제약이 추가로 붙음
  • page 캐싱에서 LRU LFU가 가능한가?
    • page fault가 나면 trap이 걸려 운영체제가 physical memory가 접근해서 가져오게된다.
    • 여기서 각 page에 대한 사용정보를 알 수가 없다.
    • 참조횟수나 최근 사용을 알 수 없다. 왜냐하면 fault가 나지 않으면 하드웨어 접근만으로 page를 가져올 수 있기 때문이다.
  • => clock algorithm

---

Clock Algorithm

출처: http://web.cecs.pdx.edu/~harry/os/slides/Ch3-MemMgmt-2.pdf

• LRU의 근사 알고리즘
• NUR(Not Used Recentlry), NRU(Not Recently Used): 최근에 사용되지 않은 페이지를 쫓아낸다.
• reference bit = 1 (최근에 참조된 페이지)
• reference bit가 0인 것을 찾을 때까지 포인터 하나씩 앞으로 이동 -> 이동하며 0으로 bit를 바꿈-> 0인 것을 찾으면 교체
• 0 이라는 의미는 한바퀴 들어오는 동안에 참조가 안된 페이지를 뜻한다. 하드웨어가 bit를 메김
• dirty bit(=modified bit)도 추가함
  • 최근에 변경된(= write 된) 페이지는 변경정보를 backing store에 써주고 꺼줘야 한다.
  • 그래서 modified bit가 0인걸 더 우선시 해서 쫓아낸다.

---

page frame의 allocation

Q. process마다 page frame을 얼만큼 할당할 것인가?

A. 각각의 프로그램마다 페이지를 나누어 주자 라는거다.

Allocation scheme(페이지를 나누는 방법)

• Equal allocation: 똑같은 개수
• Proportional allocation: 프로세스 크기에 비례하여
• Priority allocation: CPU우선순위에 따라

Global replacement

- 다른 process에 할당된 frame을 빼앗아 오는 방법

 

Local replacement

- 자신에게 할당된 frame 내에서만 replacement

---

Thrashing

출처: http://blog.naver.com/jevida/140192459532

 

• 멀티프로그래밍 degree를 올려주면 일반적으로 utilization이 증가한다.
• 하지만 어느 지점에 이르르면 thrasing이 발생하여 utilization이 감소한다.

 

• 프로세스의 원활한 수행에 필요한 최소한의 page frame 수를 할당받지 못함
• 발생 순서
  • page fault가 계속 발생(swap in / swap out)
  • OS는 degree를 높여야 된다고 판단
  • 다른 프로세스를 올림
  • 프로세스의 할당된 frame 수가 감소 -> CPU utilization 감소!

=> 그래서 멀티프로그래밍의 프로세스 개수를 정해줘야 함

Working Set 모델

Locality of reference

: 프로세스는 특정 시간동안 일정 장소(page들의 집합)만 집중적으로 참조 한다 = locality set

 

 

• Working set = Locality에 기반하여 프로세스가 일정 시간 동안 원활하게 수행되기 위한 page들의 집합
• process에 working set이 전체가 메모리에 올라와 있어야 수행되고, 그렇지 않으면 모든 frame을 반납 후 swap out (suspend)
• Thrashing을 방지함. Multiprogramming degree를 결정함.

working-set algorithm

출처: http://www.cs.uni.edu/~fienup/cs143f00/course-notes,-in-class-activitie/lec15_10-17-00.lwp/odyframe.htm

• window size(time interval)를 결정하여그 크기만큼 필요한 page 집합을 찾음
• working set에 속한 page는 메모리에 유지, 속하지 않은 것은 버림

PFF(Page-Fault-Frequency)

출처: https://copycode.tistory.com/128

• 현지 시점에서 page fault rate가 얼마나 나는지 판단
• fault rate가 상한값을 넘으면 frame 더 할당 
• fault rate가 하한값 이하면 frame 수를 줄임

---

Page Size의 결정

page size를 줄이면

• 페이지 수 증가
• 페이지 테이블 크기 증가
• 내부 조각 감소
• 꼭 필요한 정보만 올라가 메모리 이용에 효율적
• Locality는 비효율적

 

현대는 page size를 늘리는 추세로 가고있다.