[운영체제(OS)] 9장. Virtual Memory Organization(1)

8장의 contiguous, discontiguous memory allocation에 이어서 대부분의 OS에서 사용되는 Virtual memory organization, 주로 Demand paging에 대해서 알아보자.

Vitual memory concept

프로세스 이미지를 100프로 다 로딩하지 않고 프로세스를 실행할 수 있게끔하는 기법이다.
조각난 이미지를 필요할 때 memory에 로딩하기 때문에 프로세스의 용량에 구애받지 않고 실행시킬 수 있다.

• 장점
  • Easier programming : 메모리 용량 생각하지 않고 프로그램을 코딩할 수 있다
  • Higher multiprogramming degree : 메모리를 할당받는 프로세스개수를 늘려주기 때문에 성능이 향상된다. 다만 프로세스 각각을 보면 response time, turnaround time이 증가할 수 있다.
  • Less swap in/out time
• 단점
  • runtime binding을 해야하기 때문에, address mapping overhead가 발생한다.
  • page fault handling overhead
• Methods
  • Paging : 프로그램을 같은 크기의 block으로 분할
  • Segmentation : 프로그램을 다른 크기의 logical block으로 분할
  • Hybrid paging/segmentation : paging,segmentation 동시에 사용

VM은 address mapping을 어떻게 할까?

• Contiguous allocation? -> load-time binding 기법은 거의 사용할 수 없다.
• Noncontiguous allocation : run-time binding을 통한 address mapping을 사용할 수밖에 없다.

---

Block Mapping

Virtual Memory에서는 프로세스를 block단위로 쪼개고 Block map table로 관리한다.

• Virtual address v = (b,d)
  • b = block number
  • d = displacement(offset) in a block
    
• Block map table
  address mapping information을 유지해주고, 커널영역에 프로세스당 하나씩 존재한다.
  프로세스의 일부만 메모리에 로딩되기 때문에 load돼있는지 상태를 표시하기 위한 Residence bit이 사용된다.

Block mapping procedure

먼저 CPU에서 프로세스를 실행하기 위해서 virtual address를 생성한다. 메모리 접근을 하기 위해서 block map table의 residence bit을 살펴본다. 1이라면 real address 'a'에서 offset 'd'만큼 떨어진 위치인 physical address에 접근하게 된다.

residence bit == 0 이라면?
디스크에 가서 해당 block을 읽어 메모리에 가져와야한다. storage와 memory간의 데이터전송은 입출력이기 때문에 그 동안은 프로세스가 실행될 수 없다. 그렇기 때문에 이 떄 프로세스는 sleep상태가 되고 context switching이 발생하게 된다.

Pseudo-code로 요약하면 다음과 같다.

---

Demand paging

(paging으로도 얘기하기때문에 discontiguous allocation의 paging과 구분해야하는데, 최근엔 대부분 Virtual memory시스템을 사용하기 때문에 paging이라고 하면 demand paging을 생각하면 된다.)

• program을 같은 사이즈의 block으로 나눈다.

• 프로그램 실행 시 처음엔 당장 필요한 page만 로딩하고 필요에 따라 page를 추가로 로딩한다.
  

• 용어

  • page frame : 페이지와 같은 크기로 Main memory를 나눈 것
  • pager : 페이지 단위로 프로그램을 swap in/out하는 커널 모듈
  • swapper : 프로세스 전체를 swap해주는 모듈

• 특징

  • No logical partition of the program
  • Simple and efficient
  • Used in most OS
  • Complex for sharing and protection

• Address mapping

  • Virtual address v=(p,d)

  • PMT(page map table) 사용
    위에 page0,1,k만 메모리에 들어가있는 상황에 대한 PMT예시이다.

  • Address mapping기법

    • Direct mapping
    • Associative mapping : TLB(translation Look-aside buffer)
    • Hybrid direct/associative mapping

1. Direct mapping

일반 block mapping과 똑같은데, PMT가 main memory의 kernel space(PCB)에 존재한다. Pseudo-code로 보면,
이 방식은 단점이 있는데,

• PMT가 kernel space에 있기 때문에 logical address -> physical address로 변환하는 과정에서 메모리에 두 번(PMT, physical address가 있는 Memory) 접근하게 된다. Memory 접근은 수십 수백 cycle이 걸리기 때문에 성능이 저하되는 것이다.
• 또 하나의 단점은 20bit로 표현되는 page번호, 약 100만개의 entry를 갖는 PMT를 메모리에 넣기에 부담스럽다.

첫 번째 단점을 해결하기 위해 TLB를 사용하는 Associative mapping을 사용할 수 있다.

2. Associative mapping (TLB)

• TLB (Translation Look-aside Buffer) : key값을 가지고 parallel search를 할 수 있도록 해주는 하드웨어로 매우 빠르게 search하게 해준다.
• Low overhead, high speed
• 비쌈
  Direct mapping과 매커니즘은 같지만 PMT가 주기억장치에 있지 않고 TLB에 있다는 차이점이 있다.

3. Hybrid mapping

TLB전체를 모두 저장해둘 큰 용량의 TLB를 만들기가 쉽지 않기 때문에 두 기법을 적절히 합쳐서 사용하는 mapping 방법이다.

• direct + associative mapping 기법을 동시에 사용한다.
• Small TLB
  • Full PMT : memory의 kernel space에 유지한다.
  • 자주 사용되는 page entry만 뽑아서 TLB에 저장한다.

TLB를 먼저 확인해주고, 있다면 residence bit을 검사해주는데, hit ratio가 90프로 이상으로 잘 나오기 때문에 대부분 1이다. TLB에 없다면 direct mapping 기법을 사용해 메모리의 PMT에서 가져와서 TLB로 이동시켜준다.

Effective memory access time (EAT) 계산

TLB search : 20ns
memory acess time : 100ns
라고 가정했을 때,

• TLB hit ratio : 80%
  • EAT = 0.8(20+100) + 0.2(20+100+100) = 140ns
  • 40% slowdown in memory access time
• TLB hit ratio : 98%
  • EAT = 0.98(20+100) + 0.2(20+100+100) = 122ns
  • 22% slowdown in memory access time

---

TLB말고도 address mapping 속도 개선을 위해 사용되는 방법들을 간단하게 보자

• Page-table registers

  • paging address translation을 효율적으로 할 수 있는 high-speed logic 레지스터다.
  • Context saving시에 Page-table register도 저장해야한다.
  • privileged instruction으로 둬서 page map table 접근을 빠르고 안전하게 실행한다.

• Other page table structures <- page 크기 관련

  • Hierarchical paging
    Virtual address가 32-bit이라고 가정할때, 다음과 같이 20bit가 page 번호를 저장하는데 사용되고, 12bit는 offset을 저장하는데 사용된다.

    

    앞서 살펴본 것처럼 20bit면 대략 2^(20-1), 백만개 정도의 페이지 번호가 생성될 수 있는데 너무 많아 저장이 힘들기 때문에 20bit를 10bit, 10bit로 나눠서 관리하는 기법이다.
    이런식으로 2-level로 계층화시켜서 관리해 메모리에 모든 page table을 로드해둘 필요가 없도록 한다.

  • Hashed page table

  • Inverted page table
    보통 프로세스마다 page table을 하나씩 갖지만 Inverted page table은 시스템에 하나의 page table을 유지시키는 방법이다. 원래는 residence bit를 확인했지만, 이 기법에서는 virtual address의 (pid , p)를 Inverted page table에서 찾고 있다면 그 주소를 기반으로 physical address와 매핑시키는 방법을 사용한다.

    • 단점
      search했을 때 없다면 page fault가 발생하는데, Inverted page table은 프로세스의 모든 정보를 담고 있지 않기 때문에 어딘가에서 추가로 정보를 읽어 Memory에 올려주고 inverted page table도 업데이트 해줘야하는 과정이 복잡하다는 단점이 있다. 추가로 search time하는 시간이 있기 때문에 성능이 조금 저하된다.

---

Issues in Demand Paging

Demand paging기법이 해결해야할 몇 가지 이슈들이 있다.

Issue 1. Page Sharing

라이브러리 함수같이 공용으로 사용하는 자원은 프로세스 이미지에 가지고있는 것보다 메모리 한 부분에 sharable pages들을 올려놓고 같이 사용하도록 하는 것이 유리하다.

• Sharable pages

  • Data page

    • Read-only data : 무제한 접근 가능
    • Read-write data : 데이터가 변경될 수도 있기 때문에 concurrency control을 해야한다.
      Data page의 경우 간단히 PMT에서 page frame number를 공유 datapage 주소로 저장, 매핑함으로써 간단하게 구현할 수 있다.

  • Procedure pages : Pure code(reentrant code) <- 실행중에 자기 코드를 절대 바꾸지 않는 코드로, 있는 그대로 실행만 하는 코드로만 구성되어있어야 함
    

    Data page가 아닌 code page를 실행하는 page일 경우 문제가 발생할 수 있다. 위 예시처럼 코드 영역에 branch가 있다면 p1입장에서는 jump 주소가 k1이여야 정상적으로 실행되고, p2 입장에서는 jump주소가 k2여야 정상적으로 실행된다.

    그렇기 때문에 코드 페이지를 공유하는 경우에, 해당 페이지를 공유하려는 프로세스들은 아래 예시처럼 항상 같은 page frame 주소를 사용해야만한다.

Issue 2. Page Fault Handling

Virtual memory시스템을 사용하면 하나의 기계어 명령을 실행하는 도중에 page fault가 발생했을 때 문제가 생길 수 있다.ADD 명령어는 위와같은 순서로 실행된다. 기계어 명령어는 atomic하게 실행되어야하기 때문에, 실행 도중에 page fault가 발생하게 된다면,
excepttion handling으로 fetch할 때 증가시켰던 program counter 값을 원위치로 복구시킨 다음 instruction을 restart해줘야한다.

즉 fetch 뿐만 아니라 기계어명령어를 실행하는 도중 CPU나 메모리에 영향을 준 값들을 모두 원상 복구 후에 context switching을 해야한다.

Issue 3. Effective access time

page fault로 인한 EAT(effective access time)에 대한 이슈다.

Memory access time = 100ns
Average paging service time : 8 millisec
page fault rate : p (0<= p <= 1)

이렇게 가정한다면,
EAT = (1-p) x ma + p x pagingTime
= (1-p) x 100 + p x 8,000,000 = 100 + 7,999,900 x p
-> page fault(p)가 1/1000 일때, EAT = 8.1 microsec

1/1000의 낮은 확률로 page fault가 발생하는데도 80배가 느려진다.
1분 걸리는 process를 virtual memory기법을 사용하면 80분이 걸린다고 생각하면 너무하다.

10프로 정도만 성능저하가 있도록 하는 page fault 확률을 위 방식대로 계산해보면
p = 1/800,000 가 돼야한다. 이렇게 page fault를 줄이는 방법은 10장에서 다룰 예정이다.

Issue 4. Copy-on-Write Scheme (CoW)

paging system에서 fork()를 할때는 CoW기법을 사용한다.

• fork() : parent process의 모든 정보를 copy해서 child를 만드는 함수다.
• with copy-on-write scheme
  parent의 자원을 모두 복사해서 새로운 process를 만들지 말고, child가 parent의 page를 그대로 사용하도록 만드는 방법이 Copy-on-Write 기법이다.
  copy-on-write 기법을 사용해 fork()하면 이렇게 초기엔 부모의 page를 공유하는 상태다.아직 copy하진 않았다.공유하고 있는 상태에서 parent나 child가 write하면 그때 copy해서 다른 page를 쓰게한다.