[OS] Cache and Virtual Memory

이 글은 포스텍 박찬익 교수님의 CSED312 운영체제 수업의 강의 내용과 자료를 기반으로 하고 있습니다.

지난번 OS 포스트가 무려 예상 읽는시간 19분을 달성했다.

그렇게 오래 걸린 글은 난생 처음이었다.

근데 이번 포스트는 지난번 보다 더 어려울 것 같다.

PPT 순서가 너무 꼬여있다.

이전에는 그래도 나름 전공책 순서를 따라가기라도 했는데, 이번 PPT는 아예 완전 섞어놨다.

이래서 OS 글쓰기가 참 싫다..

1. Demand Paging

지난 포스트에선 Address Translation Technique이 제공하는 몇가지 기능들에 대해 알아보았었다.

오늘은 아래의 남은 기능들에 대해서 알아볼 것이다.

• Demand Paging
• Memory mapped files
• Modified bit emulation
• Use bit emulation

가장 먼저 알아볼 것은 demand paging이다.

프로그램이 disk에서 memory로 로드되는 상황을 생각해보자.

가장 간단한 구현 방법은 전체 프로그램을 memory에 올리는 것이다.

그러나 프로그램을 실행하는데에 있어서 굳이 전체 프로그램을 memory에 올려야만 할까?

필요한 것만 그때그때 올리면 훨씬 더 효율적이지 않을까?

이 아이디어가 바로 demand paging이다.

Demand-paged virtual memory에서 page는 프로그램이 실행되면서 해당 page가 필요해질 때에 비로소 로드된다.

따라서 프로그램이 실행될 동안 한 번도 접근하지 않은 page는 memory로 로드되지 않는다.

이를 통해 memory 공간을 효율적으로 사용할 수 있고, 더 많은 프로그램을 동시에 실행할 수 있게 만든다.

Demand paging 구현의 핵심은 page fault trap이다.

Page fault는 memory에 적재되지 않은 page를, 즉 invalid page를 접근하려고 할 때 발생한다.

Page fault handler는 이 상황을 두 경우로 나누어 처리한다.

1. Illegal reference

   Abort

2. Legal but not-in-memory

   Bring page to memory from disk, Set valid bit in page table

2번 과정이 demand paging의 구현의 핵심이다.

OS는 모든 page를 처음에 invalidate 상태로 초기화한다.

이후 page에 처음으로 접근한다면 page fault가 발생할 것이고 2번 과정에 의해 demand paging이 구현되는 것이다.

구체적으론 위 그림의 순서대로 일어난다.

그런데 재밌는 점은 HW-loaded TLB인지 SW-loaded TLB인지에 따라 과정이 약간 다르다.

• Demand Paging in HW-loaded TLB

  1. TLB miss
  2. Page table walk
  3. Page fault
  4. Trap to kernel
  5. Convert virtual address to file + offset

     Page data is part of file in secondary storage(disk). File could be program file, swap file or some other files.

  6. Allocate page frame (Evict page if needed)

     We have to make empty room first to write data from disk.

  7. Initiate disk block read into page frame
  8. Disk interrupt when DMA complete
  9. Mark page as valid
  10. Resume process at faulting instruction
  11. TLB miss
  12. Page table walk to fetch translation
  13. Execute instruction

  
  12, 13 번 과정을 보면, 다시 TLB miss가 일어났다.

  왜 이렇게 될까?

  만약 page fault(SW)가 발생하지 않았다면 HW가 translation을 완료한 다음 TLB에 로드를 했겠지만, page fault(SW)로 과정이 넘어갔으므로 그렇게 하지 못한 것이다.

  그러면 SW가 translation (page table walk)를 담당한다면 TLB도 로드할 수 있을 것이다.

  이것이 Demand Paging in SW-loaded TLB와 in HW-loaded TLB이 가지는 차이점이다.

• Demand Paging in SW-loaded TLB

  1. TLB miss
  2. Trap to kernel
  3. Page table walk
  4. Find page is invalid
  5. Convert virtual address to file + offset

     Page data is part of program file in secondary storage (disk)

  6. Allocate page frame (Evict page if needed)

     We have to make empty room first to write data from disk

  7. Initiate disk block read into page frame
  8. Disk interrupt when DMA complete
  9. Mark page as valid
  10. Load TLB entry
  11. Resume process at faulting instruction
  12. Execute instruction

  
  보다시피, SW-loaded TLB에서는 SW가 translation을 담당하므로 TLB miss가 난 후 Page table walk가 아닌 kernel trap이 발생하게 된다.

  이 Trap handler에서 translation을 마친 뒤, TLB에 load를 하므로 이후에 또 TLB miss를 발생시키지 않는다.

  이것만 보면 이게 무조건 좋아보이지만, 기본적으로 SW는 HW보다 느리다는 사실을 까먹으면 안된다.

한편 위 과정에서 눈여겨봐야 할 부분은 Allocate page frame 과정이다.

괄호에서 언급했듯, 만약 free space가 없다면 page를 하나 버려서 공간을 비워줘야 한다.

이 Eviction 과정이 상당히 까다롭다.

일단 버릴 페이지를 어떤 기준으로 골라야 하는지도 꽤 어려운 문제이다.

이에 관해서는 3. Page Replacement Policy에서 얘기하도록 하고 지금은 어떻게 잘 골랐다고 해보자.

그러면 우선 이 old page를 가리키고 있는 모든 page table entries를 invalidate 해야한다. (여기서 core map이 사용된다)

거기에 추가로 TLB shootdown을 통해 모든 TLB에서 관련된 entry를 지워야 한다.

그리고 마지막으로 old page가 dirty page인 경우 disk로의 write back도 해야한다.

그런데 마지막 과정에서 약간 의문이 든다.

어떻게 page가 dirty인지 알 수 있을까?

가장 효율적인 방법은 page table entry에 해당 page가 modified 되었는지 표시하는 additional bit를 저장하는 것이다. (a.k.a bookkeeping)

이 additional bit, 즉 dirty bit는 OS에 의해 0으로 초기화 된다.

이후 해당 page로의 wirte 가 발생하면 HW에 의해 자동으로 1로 바뀌며 dirty 임을 표시하는 것이다.

한편 TLB는 page table entry의 copy를 저장하므로, TLB도 당연히 dirty bit을 가진다.

주의할 점은 TLB의 dirty dit가 0에서 1로 올라갈 때 이와 연관된 page table entry도 업데이트 해야 한다는 점이다.

참고로 dirty bit 뿐만이 아니라 해당 page가 최근에 used 되었는지 표시하는 used bit도 같이 저장하는 편이다.

아래의 두 그림은 first store instruction이 발생했을 때의 TLB, page table, memory, disk의 동작을 보여준다.

다시 질문으로 돌아와서, 어떻게 page가 dirty(modified)인지 알 수 있을까?

한 page를 가리키는 여러개의 page table entry가 존재할 수 있으므로, 이 여러개의 entry 중 dirty bit가 1인 entry가 하나 이상 존재한다면 modified라고 판단한다.

반대로 모든 entry의 dirty bit가 0이라면 unmodified라고 판단한다.

Emulating

재미있게도, hardware support for a dirty/use bit가 꼭 필요한 것은 아니다.

OS는 dirty/use bit를 access permission을 이용해서 dirty/use bit을 emulate(모방)할 수 있다.

구체적은 구현법은 TLB의 종류에 따라 두 가지로 나뉜다.

• Emulating modified/use bit (HW loaded TLB)

  Page table access permission을 통해 dirty bit를 모방하는 것이 핵심 아이디어다.

  동작 과정은 아래와 같다.

  • 모든 clean page를 read-only로 초기화한다.

  • Page로의 first write가 발생하면, HW에 의해 memory exception이 발생한다.

  • OS는 page의 permission을 read-write로 바꾸어 dirty 임을 기록한다.

  보다시피, true page table permission과 current page table permission 두 가지를 유지해야 한다.

  Used bit를 구현하는 것도 거의 동일하다.

  다만 first read/write를 모두 감지해야 하기 때문에, page를 read-only가 아니라 invalid로 초기화해야 한다.

  • 모든 clean page를 invalid로 초기화한다.

  • Page로의 first read/write가 발생하면, HW에 의해 exception이 발생한다.

  • OS는 page의 permission을 read or read-write로 바꾸어 used 임을 기록한다.

• Emulating modified/use bit (SW loaded TLB)

  SW loaded TLB에서는 TLB miss 또는 permission exception이 발생했을 때 trap to kernel이 발생한다.

  그래서 HW loaded TLB는 달리, page table walk 까지 가지 않고 trap handler에서 곧바로 emulation을 구현할 수 있다.

  구체적인 동작 과정은 아래와 같다.

  • On a TLB read miss
    • If page is clean, load TLB entry as read-only
    • If page is dirty, load as r/w
    • Mark page as recently used
  • On a TLB write to an unmodified page
    • Kernel marks page as modified in its page table
    • Reset TLB entry to be read-write (Already entry is in TLB, so re-set)
    • Mark page as recently used
  • On a TLB write miss
    • Kernel marks page as modified in its page table
    • Load TLB entry ad read-write (No entry in TLB, so load)
    • Mark page as recently used

2. Memory-Mapped Files

File I/O를 수행하는 두 가지 모델이 있다.

1. Explicit read/write system call

   • Read/write system calls allow the program to work on a copy of file data

   • Read syscall: Copy chunks of file data into buffers in the program’s address space

   • Write syscall: Use to write changes back to the file. Write the data from the copy of file in program buffers out to disk.

   • Simple to understand, reasonably efficient for small file.

2. Memory-mapped files

   Map file contents into the program’s virtual address space

   

   이 모델의 핵심은 file을 program segment로 간주하는 것이다.

   다시 말해, file을 별도의 data structure로 생각하지 말고 그냥 우리가 이제껏 해왔던 paging을 적용해 file을 page 단위로 잘라서 여타 page와 동일하게 동작하게 하는 것이다.

   곧, 1번처럼 복잡하게 copy를 할 필요 없이, 그냥 physical memory를 disk에 대한 write-back cache로 간주하여 direct access를 할 수 있는 것이다.

   이러면 우리가 이제까지 해왔던 demand paging, copy on write 등의 feature들의 혜택을 그대로 누릴 수 있다!

   이외에 어떤 장점들이 있을까?

   • Zero copy I/O

     The operating system does not need to copy file data from kernel buffers into user memory and back; rather, it just changes the program’s page table entry to point to the physical page frame containing that portion of the file.

   • Pipelining

     The program can start operating on the data in the file as soon as the page tables have been set up; it does not need to wait for the entire file to be read into memory.

   • Interprocess communication

     Two or more processes can share information instantaneously through a memory-mapped file without needing to shuffle data back and forth to the kernel or to disk

   • Large files

     As long as the page table for the file can fit in physical memory, the only limit on the size of a memory-mapped file is the size of the virtual address space

3. Page Replacement Policy

On a page eviction, how do we choose which entry to replace?

자 이제 1번에서 예고했던 Page Replacement Policy에 관해서 다뤄볼 차례이다.

지지난 포스트의 scheduling policy와 큰 차이는 없다.

Clock algorithm 정도만 제대로 이해하면 된다.

FIFO

Replace the entry that has been in the cache the longest time

MIN, LRU, LFU

• MIN

  Replace the cache entry that will not used for the longest time into the future

  • Optimal: Minimum cache miss

  • Not feasible: Have to predict future

• LRU

  Replace the cache entry that has not been used for the longest time in the past

  • Approximation of MIN
• LFU

  Replace the cache entry used the lest often (int the recent past)

Belady’s anomaly

여기서 질문!

Page frame을 더 많이 만들면 miss가 더 적게 날까?

되게 당연해보이지만, 놀랍게도 정답은 그렇지 않다

FIFO policy를 사용한다고 하자.

• 3 page frames
  • A, B, C, D, A, B, E, A, B, C, D, E
  • 9 page fault(miss)
• 4 page frames
  • A, B, C, D, A, B, E, A, B, C, D, E
  • 10 page faule(miss)

보다시피, page frame의 수를 늘렸지만 오히려 page fault의 수가 늘어났다!

이같은 기이한 현상을 belady’s anomaly라고 한다.

Clock Algorithm

자세히 다루지는 않았지만, LRU를 구현하기 위해서는 counter, stack 등 여러가지 HW support가 필요하다.

이걸 전부 지원하면 LRU를 쓰면 되겠지만, 그렇지 않은 경우에는 LRU를 근사하는 알고리즘이 필요하다.

이것이 clock algorithm이다.

Clock algorithm은 page frame을 circular list로 관리한다.

Page fault가 일어나면, clock algorithm은 page frame circular list를 시계 방향으로 돌면서 아래의 동작을 수행한다.

• If used bit == 1, change to 0 and go on next page frame
• If used bit == 0, select this page frame to replace

이때, used bit가 1인 page에게 한 번 기회를 준다는 의미에서 second chance algorithm이라고 불리기도 한다.

N-th Chance Algorithm

Second chance가 있으면 N-th chance도 있어야 하지 않을까?

N-th chance algorithm은 second chance algorithm을 약간 확장한 것이다.

판단 기준을 used bit가 아닌, 최대 N까지 늘어나는 정수로 두는 것에 불과하다.

한편으론 N번 돌 때까지 쓰이지 않은 frame을 버린다고 해서 not recently used policy 라고 부르기도 한다.

Implementation Node

Clock 과 N-th Change algorithm을 구현하는 방법은 크게 두가지로 나뉜다.

• Synchronously

  • Use in Pintos project 3

  • Sync = Run algorithm only when needs (page fault occurs)

  • In page fault handler, if evicion needs, run algorithm find next page to evict

  • If dirty, write back to disk

• Asynchronously

  • Async = Run in background

  • With enhanced second-chance algorithm

    1. (0, 0) neither recently used nor modified

    2. (0, 1) not recently used but modified

    3. (1, 0) recently used but clean

    4. (1, 1) recently used and modified

  • Create a thread to maintain a pool of (0, 0) pages

  • Periodically run algorithm below

    • If found (0, 1) page, write back to disk and change to (0, 0)

    • If found (0, 0) page, mark as invalid and move to pool

  • On page fault, check if requested page is in pool

  • If exist, change to (1, 0) or (1, 1) and remove from pool (recover page)

  • If not exist, select any page in pool, and evict (replace page)

4. Allocation of Frames

주의

이 챕터에서는 page와 page frame의 차이를 엄밀하게 구분하고 있지 않다.

원래대로라면 관리 측면에선 page를, 할당 측면에서는 frame이라는 단어를 써야한다.

그러나 PPT는 이를 엄밀하게 구분하지 않고, 그냥 page를 메모리 단위로서의 의미로 사용하고 있으므로, 이를 그대로 차용하였다.

Frame은 PM! Page는 VM 이런 식으로 구분하지 말고, 그냥 둘 다 메모리 단위라고 받아들이면 된다.

Eviction에 대해선 전부 알아보았고, 이제 allocation 자체에 문제를 알아보자.

궁극적으로 우리는 아래의 질문에 답하는 것을 목표로 한다.

How many frames allocated to each process?

Minimum Number of Frames

Frame allocation의 기본 제약은 Process가 무사히 동작하기 위한 최소한의 수 이상을 할당해야 한다는 것이다.

왤까? 가장 주된 이유는 성능 향상을 위해서이다.

최소한의 수가 보장되지 않는다면 page fault가 일어날 가능성이 매우 높고, 이로 인해 process의 성능이 크게 하락하기 때문이다.

이때, process의 실행단위는 instruction 이므로 Process가 무사히 동작하기 위한 최소한의 수는 single instruction을 실행하기 충분한 양의 page를 의미함을 알 수 있다.

아키를 수강했다면 알겠지만 single instruction을 실행하는데 필요한 frame의 수는 computer architecture에 의해 결정된다.

예를 들어, IBM 370라면 SS MOVE instruction이 총 6 frame를 사용하므로 Process에게 최소 6 frame를 할당해줘야 한다.

Allocation Algorithms

제약은 알아봤으니, 이제 할당할 차례이다.

Physical memory(frames)라는 한정 자원을 어떻게 process들에게 잘 나눠주느냐? 가 메인 문제다.

이 문제를 해결하는 알고리즘은 고정된 property만 사용하는 Fixed allocation과 임의로 지정할 수 있는 property(ex: priority)를 사용하는 priority allocation으로 나뉜다.

• Fixed allocation

  • Equal allocation

    Allocate equal size of frames to proccesses (1/n)

  • Proportional allocation

    Allocate according to the size of proccess

    

• Priority allocaion

  the ratio of frames depends on the priorities of processes or on a combination of size and priority.

Global versus Local Allocation

Frame allocation에 있어서 또 한가지 중요한 요소는 page replacement이다.

Multiprocess 환경에서 page replacement policy는 크게 두가지로 나뉜다.

• Global replacement

  Select frame from the set of all frames; One process can take a frame from another

  • ex) In priority allocation, select for replacement a frame from a process with lower priority number

  • 장점
    • Greater system throuput
  • 단점
    • Process cannot control its own page-fault rate

      The set of pages in memory for a process depends not only on the paging behavior of that process but also on the paging behavior of other processes

• Local replacement

  Select frame from its own set of allocate frames

  • ex) In priority allocation, select for replacement one of its frames.

  • 장점
    • Paging behavior is affected by only own process
  • 단점
    • Less system throuput (Less use of pages)

일반적으로 성능의 이점 때문에 Global replacement를 채택하는 편이다.

5. Thrashing

그런데 이렇게 할당을 하고 나면 위에서 알아보았던 minimum Number을 보장받지 못하는 (low priority) process가 생길 수 있다.

아마 이 process는 page fault가 곧바로 발생할 것이다.

그러면 instruction을 실행하기 위해 in-active인 page를 evict해야 한다.

그런데 In-active page는 이후에 다시 접근할 가능성이 높은 page이므로, 아마 또다시 page fault가 발생할 것이고 그러면 또 다른 In-active page를 evict해야 한다.

그러면 또 다시 page fault가 발생할 것이다.

이렇게 계속해서 page fault가 발생하는, 일명 high paging acitivy를 thrashing이라고 한다.

Thrasing이 발생하는 원인은 크게 세가지가 있다.

• Process doesn’t reuse memory, so caching doesn’t work

• Process does reuse memory, but it does not fit

• Individually, all processed fit and reuse memory but too many for system

이 중 첫 번째와 두 번째는 process 자체의 문제이므로 해결하기가 어렵다.

그러면 세 번째 문제는 어떻게 해결할 수 있을까?

Working-Set Model

세 번째 문제를 해결하기 위해선 process가 얼마만큼의 frame을 사용하는지 알아야 한다.

그런데 그걸 어떻게 알 수 있을까?

몇 가지 방법이 있지만, 우리가 알아볼 것은 Working-Set Model이다.

Working-Set이란, locality에 기반하여 process가 일정 시간동안 원활하게 수행되게 위해 한꺼번에 메모리에 올라와 있어야 하는 페이지들의 집합을 말한다.

Working-Set Model에서는 이 working set을 process가 할당받아야 하는 최소한의 양, 즉 threadhold로 본다.

따라서 Working-Set Model은 working set이 전부 올라와 있지 못한 process를 swap-out 시키게 되고, 이를 통해 thrashing을 방지하고 multiprogramming degree를 조절할 수 있다.

참고로 working set은 시간에 따라 변화한다.

Page Coloring

한편 프로그램에 어느 위치의 frame을 할당해주는지도 성능에 있어서 꽤 큰 영향을 미친다.

예를 들어 8MB directed cache와 4KB page가 주어졌다고 하자.

1 of every 2K pages는 cache 상에서 같은 라인에 위치한다.

그런데 이 같은 라인에 위치하는 page들을 프로그램에 할당했다고 하자.

그러면 계속해서 cache eviction이 발생할 것이므로 성능이 급격하게 떨어지게 된다.

이런 문제를 방지하기 위해 OS는 page coloring 이라는 기법을 사용한다

Page coloring은 physical page frames를 어떤 cache bucket에 들어갈지를 기준으로 구분하는 걸 말한다.

예를 들어 2MB 8-way set associative cache와 4KB page가 주어졌다고 하자.

그러면 page를 2 * 2^20 / 4 * 2^10 / 8 = 64 개의 color(or separate set)로 구분하게 된다.

Page coloring을 사용하는 OS는 (프로그램) page를 할당할 때, 이 color가 최대한 겹치지 않도록 할당한다.