Operating System: Virtual Memory (Chapter 8)

Virtual Memory

• physical memory보다 더 큰 프로세스를 돌리고 싶어졌다
• 그래서 'process 전체가 memory에 올라와야 실행 가능하다'라는 대원칙을 깨리고 하면서 탄생한 것이 virtual memory
• CPU는 virtual memory만 알고 있고, OS가 virtual memory와 physical memory 사이 연결을 돕는다
• memory space가 무한대로 늘어나는 것. memory utilization이 증가한다

Demanding Paging

• Virtual memory의 핵심 기술
• CPU가 요청할 때, OS가 해당 page를 memory에 올려주는 것 
• 장점: less I/O needed, less memory required, fast response time, more processes
• Lazy swapper: process 실행 시, 전체를 다 통으로 memory에 올리는 것이 아니라, CPU가 필요로하는 것만 그때 그때 올리는 것. (필요로하지 않는 애는 계속 올라오지 않음)
• 또다른 장점: Copy-on-Write
  • parent process에서 fork해서 생긴 child process는 서로 virtual memory address는 다르지만, 같은 physical memory address를 참조하고 있다
  • 그러다가 두 process 중 하나가 reference에 대해 write를 시도하면, 그 시도한 process가 (그때서야) copy된 physical memory를 갖는다
  • 장점: memory 효율 증가, response time 감소
  • 단점: write하는 순간에 성능 저하 (시간 오래 걸림)

Page valid-invalid bit

• page table에서 해당 page의 상태를 표시하는 bit
• 아래 세가지 의미를 지닌다
  • illegal: page에 접근할 수 없는 상태
  • not in memory: memory에 해당 page가 올라오지 않는 상태 >> page fault를 일으킴
  • obsolete: memoery에 page가 있긴 한데 뭔가 잘못된 상태 >> page fault를 일으킴

Page fault

• page의 valid-invalid bit이 not in memory나 obsolete을 의미해서, physical memory에 해당 page를 (re)load 해야하는 상황
• 이 때, OS는 kernel mode로 전환되어, page fault handler를 작동시킨다
• page fault handler 작동 과정
  1. page table에서 invalid bit 확인 (illegal -> abort, not in memory/obsolete -> continue)
  2. OS가 kenrnal mode로 전환 (page fault trap = page fault handler 시작)
  3. disk로 가서 page 가져옴 (I/O 발생)
  4. 동시에 physical memory에 free frame이 있는지 확인, 있으면 거기에 해당 page 넣어줌
  5. page table에서 bit을 valid로 전환 (이때 process state는 waiting -> ready queue로 전이)
  6. process state가 running으로 바뀌면 page fault handler의 역할은 끝난다

 

Page Replacement

• memory에 빈 공간이 없을 경우, page를 하나 memory에서 내려야 한다
• 이 알고리즘이 잘못되면, page fault가 많이 발생한다
• 따라서 최대한 page fault가 적게 일어나는 알고리즘을 찾아야한다

First in First out (FIFO)

• Belady's Anomaly: 사용가능한 frame 수가 늘어남에도 불구하고 page fault 횟수가 증가하는 이상 현상
• 즉 알고리즘을 잘 짜지 않으면, resource의 풍부함을 누리지 못한다

Least Rencently Used (LRU) Algorithm

• FIFO보다 나음
• 그러나 최근 reference된 page 정보를 담고 있는 stack을 관리/유지해야하는 overhead가 너무 크다
• 따라서 실제로 사용하기는 어려움

LRU Approximation Algorithm

• LRU랑 최대한 비슷하게 알고리즘을 짜보자는 아이디어
• LRU스럽게 만드는 대신, overhead를 최대한 줄여보자
• Valid/invalid bit 방식: overhead는 많이 줄지만, victim page의 퀄리티가 너무 떨어진다
• Additional-reference bit 방식: 8bits를 두고, 참조될 때 마다 수를 하나씩 올림
• Second-chance (clock) algorithm 방식: FIFO나 circular queue에 reference bit들이 들어있다. 해당 page를 replace해야할 때가 되면, 우선 잠시 reference bit을 확인한다. 이때 이 bit가 0이면 replace하고 1이면 기회를 한 번 더 준다. 

Physical Memory Allocation Policy

• Fixed Allocation (= local allocation): 사용가능한 frame 수 / 전체 프로세스 수 만큼을 각 프로세스에게 제공한다
• Priority Allocation (= global allocation): priority가 높은 프로세스에게 더 많은 수의 frame을 제공한다

Thrashing

• CPU가 자주 참조하는 page보다 frame 수가 적으면, 급격하게 많은 page fault가 발생하면서 CPU utilization이 저하되는 현상
• 이를 방지하기 위해서는 allocated memory size > sum of locality를 보장해야한다
  • locality (spatial locality & temporal locality)를 활용해서 window size를 잡는데, 이를 working set이라고 한다

 

Virtual Memory의 몇가지 Issue

1. Prepaging: page fault 발생 수를 줄이기 위해서 process 시작 시, 미리 page를 여러개 memory에 올리는 것

2. Page size: page size를 결정하는 문제. 최근 트랜드는 larger page size를 선호한다. (장: page memory size 감소, page fault 감소, 단: internal fragment 증가)

3. TLB Reach = (TLB Size) X (Page Size): TLB에 의해서 접근 가능한 memory size를 의미. 당연히 클 수록 전체 속도가 빨라짐

4. Progrma Structure: 프로그램을 어떻게 코딩하느냐에 따라서 page fault 발생 수가 차이난다

for(j=0; j<128; j++)
	for(i=0; i<128; i++) //page fault
    	data[i][j] = 0

for(i=0; i<128; i++) //page fault
	for(j=0; j<128; j++)
    	data[i][j] = 0

 

위에는 page fault 가 128 x 128회 발생하고 아래는 128회만 발생