[운영체제/OS] Virtual-Memory Management

 

Virtual -Memory Management에 대해서 알아보기 전, 배경 지식부터 알아보자.

Swapping

: process size가 physical memory 보다 클 때, whole process를 백업 저장소에 일시적으로 swap 한 후, 계속 실행하기 위해 다시 memory로 swap한다.

• swap device - usually HDD, SDD, or Flash

하지만, Swapping은 context switching time이 굉장히 크다. 따라서, 현대 OS들은 swapping을 피하려고 한다.

이와 같은 문제를  해결하기 위해 Demand Paging을 사용한다.

 

 

이제 본격적으로 Demand Paging에 대해서 알아보자.

Demand Paging

: 사용하는 페이지, 즉 필요한 페이지만 main memory에 load 시킨다.

즉, 필요하지 않는 page는 disk에 존재하고, 필요한 page는 memory에 존재한다.

장점 ) physical memory 보다 큰 크기의 process를 할당 받을 수 있다

• Less I/O needed from disk to load memory
  • program을 load하는 데 빠른 반응속도
• Less memory needed
  • 큰 program들을 부분 부분 나눠 load한다
• Better multi-program

이떼, memory에 page가 존재하는지를 나타내는 것이 Valid-Invalid Bit이다. 

Valid bit: memory에 존재

Invalid bit: memory에 존재하지 않음

 -> page fault 발생 -> trap 발생 -> Disk 의 swap space에 접근해야함 -> Disk I/O가 필요

 

Page fault

•  invalid page를 참조하면 발생
• OS에게 trap이 발생할 것이다 (trap = software interrupt)
• page fault rate (0<= p <=1)
  • if p=0, no page faults
  • if p=1, every reference is a fault
• Effective Access Time (EAT) for demanding paging

 

OS가 page fault 다루는 법

1. OS가 page table를 확인한다
2. invalid bit 통해 memory에 page가 존재하지 않는다는 것 발견 -> trap 발생
3. Page 는 disk에 있는 swap space에 존재 - physical memory로부터 free frame을 가져와야 함 
4. disk로부터 physical memory frame으로 miss되어 있던 page를 가져온다.
5. page table reset 하여 valid bit으로 page 존재한다는 것을 확인한다
6. pagefault로 인해 실행하지 못했던 명령을 다시 수행한다.

 

Demand paging usage 

 

1. Heap/Stack
   • Heap: grow upward in memory as it is used for dynamic memory allocation
   • Stack:.grow downward in memory through successive function call
   • Do not need to be allocated physical frames for heap/stack at the beginning -  힙/스택이 증가하는 경우에만 실제 물리적 프레임이 필요함
   • heap 또는 stack이 확장되어야만 physical page를 요구한다.
2.  Dynamically linked libraries (DLL)
   • Library linking 은 실행시간이 될 때까지 지연된다.
   • DLL에 해당하는 코드는 load 시키지 않다가, DLL 부분이 필요할 때 load하여 실행한다
   • Stub is included in binary image for each DLL reference // DLL을 reference 하는 코드
     • stub : piece of small code that indicates how to locate appropriate routine
3. Copy-on-Write , fork()

• 처음 child가 생성되면 parent와 메모리상에서 같은 page를 갖기 때문에 처음에만 parent의 page를 share하도록 한다.
• 그러다가 child page가 수정된다면, 그 경우에만 새로운 page를 생성하여 child page를 copy한다.
• child page를 수정하지 않는다면 physical page 를 굳이 늘리지 않아도 된다.
• 만약 child가 exec()을 사용한다면, free page를 demand paging을 이용하면 된다.

 

 

 

Page replacement

: free-frame list에 free frame이 없을 때, memory 상에서 앞으로 안 쓸 것 같은 page가 있다면, 해당 page를 page out 시키고, page fault가 일어난 page는 memory에 page in 시킨다.

-> Page replacement Algorithm에 따라 page out 시킬 page를 찾는다.

 

1.  disk에서 page fault가 일어난 page의 위치를 찾는다
2. free-frame list에 free frame이 있는지 확인한다
   • free-frame이 있으면, free frame을 사용한다.
   • free-frame이 없으면,  page replacement algorithm에 따라 page out 시킬 page를 선택한다.
3. page fault가 일어난 page를 읽고, page table update한다.
4. process를 다시 실행한다.

 

이때, 만약 free frame이 없다면, disk에 두 번 접근해야한다 (for page out/page in)

// page out = disk로 page out하는 과정

disk에 접근하여 write하는 과정을 줄일 수 있는 방법이 없을까 ?

 

Modify bit ( = Dirty Bit ) 을 사용하는 것이다.

이를 0으로 초기화 시켜놓고,

만약 page가 수정된 적 있으면 1로 bit을 설정하고, 수정된 page는 page out/page in 둘 다 해야한다.

만약 page가 수정된 적 없으면 0으로 bit을 설정하고, 수정되지 않아 disk에 같은 내용이 존재하기 때문에 page out 시킬 때 disk에 접근하지 않아도 되고, disk에 write하는 과정 없이 삭제해줘도 된다.

 

 

 

 

 

---

Thrashing 

: page fault가 증가하여 일정 시기가 되면 CPU utilization이 낮아지게 되는 현상

- 만약 process가 충분한 page를 갖고 있지 않는다면,

   한 process 당 얻을 수 있는 page 수가 줄어들기 때문에 page-fault rate는 매우 높아진다.

   -> 존재하는 frame을 replace 해야한다.

 

 

To prevent thrashing

• Process가 필요한 만큼 제공해줘야하는데, 그러기 위해서는 process가 얼마나 필요한지를 알아야 한다.
  • Locality (지역성) 사용
    • 지역성 : 특정 지역을 일정 시간 동안 사용
    • working-set model : 최근에 사용한 memory는 앞으로도 일정 시간 동안 사용할 것이다. 이러한 memory를 working set window에 저장한다.
      • if working-set 이 너무 작으면 locality를 제대로  확인할 수 없다.
      • if working-set 이 너무 크면 너무 옛날 locality까지 포함하기 때문에 working-set이 너무 커진다.
      • 만약 working-set이 무한대로 가면, 전체 program 저장 -> not locality
    • 필요한 frame 수 < 사용 가능한 frame 수 : Thrashing 이 일어나지 않는다.
    • 필요한 frame 수 > 사용 가능한 frame 수 : process를 suspend 하거나, swap out 함으로써 multiprogramming의 정도를 줄인다.
• • size of locality의 합 > free frame의 수 일때, thrashing이 일어난다.
   

page-fault frequency (PFF)

• If actual rate too low, process loses frame 
  • page fault ↓  = process 수 ↑ = frame 수 ↓ => process 수 ↓ = frame 수 ↑ 
  • page fault ↑  = process 수 ↓ = frame 수 ↑ => process 수 ↑ = frame 수 ↓
• If actual rate too high, process gains frame
• If page fault rate increases and not enough free frames -> thrashing 발생 -> process swap out.

 

 

 

이렇게 virtual memory와 paging 에 대해서 알아보았다.