SHPC 12 - Memory Consistency and Virtual Memory

들어가기 전에..

나는 이 내용을 슬라이드로만 공부하면서 머리가 터질 뻔 했는데, 앞부분에 약간의 정리를 해 주면 이해가 쉬울 것 같아 써 본다.

1. Program order와 execution order, observed order

이 세 개념이 다르다는 것을 알고 시작해야 했다.

1. Program order : 소스코드에 적혀있는 명령어 순서이다
2. Execution order : 실제 실행 순서이다
   • 예를 들어 최적화를 위해 실행 순서 변경, out of order execution을 한다고 하면 program order와 execution order는 달라질 수 있다.
3. Observed order : 다른 프로세서에서 관찰하는 순서이다
   • 예를 들어 write buffer를 사용한다고 하면 내부에서는 쓰기 연산이 완료되었는데 외부에서는 쓰기가 이뤄지지 않은 것처럼 보인다. 따라서 program order, execution order, observed order는 서로 다를 수 있다. Memory consistency가 관심있는 것은 observed order이다. 특정한 규칙에 의해 observed order를 예측가능하게 만들어 주는 것이 memory consistency solution들의 주 목적이다.

Memory Consistency Problem

• 공유되는 메모리에 대한 데이터 접근 순서에 따라 실행 결과가 달라지는 문제
• 원인: Reordering
  • 여러 이유로 reordering이 가능하기 때문이다
  • Compiler optimization
  • Underlying architecture
• +) 왜 문제인가?
  • 프로세서 내부에서는 execution order대로 보이는데, 외부에서는 그렇지 않을 수 있음
  • 따라서 외부 프로세서가 보는 메모리 접근 순서를 강제할 필요가 있음 → Memory consistency model의 역할

Coherency vs Consistency

• Coherency
  • Single memory location에 대해 가장 최근의 write가 여러 프로세서들에게 visible해야 한다
  • Single memory location에 대한 일관성
  • e.g. single cache block에 대한 일관성
• Consistency
  • 메모리 읽기/쓰기의 순서가 여러 프로세서들에게 일관적으로 보여야 한다
  • 여러 memory location에 대한 일관성
  • 메모리 읽기/쓰기 순서의 일관성
• 따라서 Coherence 솔루션은 Consistency에 도움이 되지 않음

Memory Consistency Models

• Memory operation의 순서를 결정하기 위한 제약 조건들을 정의
  • 언제 어떤 프로세서의 메모리 업데이트가 다른 프로세서에게 보일 수 있는가?
• 프로그래밍 복잡도와 성능 사이의 밸런스를 맞추기 위해 중요
  • 프로그래머는 이를 통해 가능한 결과값들을 예측 가능
  • 시스템 디자이너는 어떤 부분이 reordering 가능한지 알 수 있음
• 프로그래머와 시스템 디자이너간의 계약이라고 볼 수 있음
• 종류
  • Sequential consistency
  • Relaxed memory consistency
    • Processor consistency
    • Weak ordering
    • Release consistency

Sequential Consistency

Quote

[Lamport, IEEE TOC, 1979] A multiprocessor system is sequentially consistent if the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program

• Operation 간의 total order를 지킨 것과 동일한 순서가 관찰되어야 한다.
  • Total order를 지킨 것 모든 연산을 원자적으로 수행한 것 이전 연산이 끝날 때까지 기다렸다가 그 다음 연산을 수행하는 것 == program order대로 수행한 것
    • Write의 경우 오래 걸려도 커밋이 완료된 뒤에야 read를 하는 것
  • 같은 쓰레드 내의 operation은 해당 쓰레드의 program order대로 수행된다
• 그러나 꼭 total order대로 실행하지 않아도 읽기의 결과만 동일하면 될 때도 있다.
  • total order를 지켰을 때 나올 수 있는 결과의 수가 정해져 있는데, 이러한 결과에서 벗어나는 결과가 나오면 안된다는 것 뿐, 리오더링을 아예 못하는 것은 아니다
• Atomic operation + arbitrary interleaving 처럼 보여야
• 가장 비효율적인 방법

Possible Executions under Sequential Consistency(SC)

• S11 → S12 → S22 → S21
  • 0, 1은 SC를 지켰을 때와 동일한 결과
  • 따라서 이 순서도 SC를 지킨다고 볼 수 있음

Reasoning Based on SC

• X = 1 → Y = 0
  • X = 1이라는 것은 S22 → S11
  • 이는 S21 → S12를 암시하므로, Y는 0이어야 함
• X = 0 → Y = 0 or 1
  • X = 0이라는 것은 S11 → S22
  • S12와 S21의 순서는 관계없으므로, Y는 0과 1 모두 될 수 있음
• Y = 1 → X = 0
  • Y = 1이라는 것은 S12 → S21
  • 이는 S11 → S22를 암시하므로, X = 0이어야 함

Relaxed memory consistency

Processor Consistency (PC)

• Read → Read, Read → Write, Write → Write의 순서는 모든 프로세서가 동일하게 관찰할 수 있어야 한다.

Write → Read

• Write a → Read b 의 reordering을 허용 (디펜던시 있는 부분 제외)
• Write 연산이 끝나기 전에 Read 연산이 끝날 수 있다는 것
  • Write buffer with read bypassing
  • Write buffer를 이용해 write 데이터를 저장하고, Read할 때는 이 buffer 값을 읽는 방식
  • Write가 완전히 끝나기 전에도 read를 끝낼 수 있다. (즉 외부 프로세서가 보기에 read가 먼저 수행된 것처럼 보일 수 있다)
• 아래 그림에서 x, y가 shared variable이기 때문에 이에 대한 read/write만 생각하면 된다
  • 즉 S11, S21은 write, S12, S22는 read 이다

Weak Ordering

• 모든 프로그램의 순서를 relax하지만, sync operation은 relax하지 않는 ordering
• Synchronization operation을 추가하여 ordering을 못하게 막는다
  • fence opreation 등이 예시가 될 수 있음
  • 순서를 지켜야 하는 경우 (모든 프로세서에 대해 동일하게 보여야 하는 순서)
    • Sync operation → 일반적인 read/write : 동기화 연산 이후 읽기/쓰기는 동기화 연산을 기다려야 함
    • 일반적인 read/write → Sync operation : 동기화 연산 이전 모든 읽기/쓰기가 완료되어야 함
    • Release consistency와 다르게, sync() 두개 바깥의 연산을 안쪽으로 집어넣는 등의 최적화는 불가능함 (규칙에 따라 sync 이전은 이전, 이후는 이후끼리 최적화 가능)
  • 순서를 지킬 필요가 없는 경우
    • read/write끼리 순서
• 여러 개의 읽기/쓰기를 동시에 처리하는것도 허용된다
  • Read/Write latency를 숨기기 위함

Release Consistency

• Weak ordering에서 sync operation을 두가지로 정의
  1. Acquire : Read operation, lock(V)
     • lock을 잡았다
  2. Release : Write operation, unlock(V)
     • lock이 풀렸다 == write가 완료되었다
• 규칙
  • 모든 읽기/쓰기는 이전에 acquire가 있으면 그것을 기다려야 한다
    • 반대로 acquire가 자기 이전의 읽기/쓰기를 기다릴 필요는 없다
  • 모든 release는 이전에 읽기/쓰기가 있으면 그것을 기다려야 한다
    • 반대로 읽기/쓰기가 자기 이전의 release를 기다릴 필요는 없다.
  • Acquire, Release는 Sequentially consistent해야 한다.
• 많이 사용하는 consistency 모델
• 아래 그림처럼 critical section에 연산을 넣을 수는 있지만 뺄 수는 없다
  • Release 뒤에 있는 것은 앞으로 갈 수 있음 / 앞에 있는건 뒤로 못감
  • Acquire 앞에 있는 것은 뒤로 갈 수 있음 / 뒤에 있는건 앞으로 못감

Understanding RC

• release → 무조건 이전 operation이 끝나야 함. 메모리에 쓰는것 역시 다 끝나야 release됨
• 첫번째 말풍선 : release 되기 전이니 0도 되고 5도 된다
• 두번째 말풍선 : release가 끝났으니 무조건 write value가 커밋되어 있어야 한다
• 세번째 말풍선 : acquire 전이라서 아무거나 된다
• 근데 프로세서 본인이 쓴 것은 본인에게 보여야 하는 걸 보면 (x = 7) 아마 뭐 버퍼같은걸 쓰고있는 상황인듯함

Virtual Memory

• 목적

1. Management: 프로세스별로 메모리 공간을 제공하여 혼자 시스템을 쓰는 것처럼 보이게 함 → 프로그래밍 및 메모리 관리가 쉬워짐
2. Protection: 다른 프로세스가 주소공간을 침범하지 못하게 함
3. Cache: 메인 메모리를 디스크의 캐시처럼 사용할 수 있도록 함

• 구성은 이런식으로 될 수 있다.
• 앞의 캐시는 logical address로 접근, 뒤는 physical로 접근하게 될 것

MMU and Pages

• MMU: 메인 메모리의 페이지 테이블을 보고 Virtual address를 physical address로 변환하는 역할 수행

Page table

• Physical address와 virtual address의 매핑 정보
• 메인 메모리에 저장
• CPU의 Page Table Base Register(PTBR)가 page table 주소 저장
• Page table entry(PTE)로 구성
• 계층적 구조를 갖기도 함
  • 전체 address space를 하나의 페이지 테이블에 담는 것은 너무 크기 때문
  • e.g. 32bit address space, 4KB pages, 4B PTE의 경우 page table의 크기는?
    • 2^20 * 4 = 4MB
  • 페이지 테이블에 대해서도 demand paging을 하는 것

Demand paging

• 페이지를 실제로 사용하기 전에는 allocation하지 않는것
• Page fault가 나기 전까지는 swap in 하지 않음
• Swapping (Paging)
  • 메인 메모리와 스토리지 사이에 page를 주고받는 것
  • OS의 page fault handler가 담당

Address Translation

• Virtual page의 세가지 종류
  • Unallocated: 아직 접근하지 않아서 물리 메모리가 할당되지 않음
  • Cached: 메인 메모리에 있음
  • Uncached: 디스크에 있다

Page Hit

1. CPU가 MMU에게 Virtual address의 변환을 요청
2. MMU는 해당 address에서 page table entry address를 구해 page table을 확인
   • Page table은 메인 메모리에 있음
   • Page table entry address (PTEA): PTBR + VPN
3. 메인 메모리의 page table에서 PTE를 읽음
4. PTE로부터 physical address를 구해서 메인 메모리에 접근
5. 데이터 전송

Page Fault

1. CPU가 MMU에게 Virtual address의 변환을 요청
2. MMU는 해당 address에서 page table entry address를 구해 page table을 확인
   • Page table은 메인 메모리에 있음
   • Page table entry address (PTEA): PTBR + VPN
3. 메인 메모리의 page table에서 PTE를 읽음
4. Valid bit가 0 → Page Fault Exception 발생
5. OS의 page fault handler가 victim page를 골라 디스크로 swap out
6. OS의 page fault handler가 대상 page를 swap in 하거나 할당
7. OS의 page fault handler가 PTE 업데이트 후, 실패한 instruction을 다시 시작
8. (Page hit와 동일한 과정 진행) CPU가 MMU에게 Virtual address의 변환을 요청 …

Page Replacement Policies

• Victim page를 어떻게 정할 것인가?
• e.g. LRU, FIFO, Second change, …
• 리눅스는 Clock 알고리즘 사용
  • 
  • Hand : 현재 접근하는 페이지
  • Reference bit : 한번 access 될 때마다 1으로 만들어주고, victim을 찾을 때 0으로 만듬
    • 디폴트는 0
  • Victim을 찾는 과정
    • hand부터 차례로 찾으면서 reference bit가 1인 페이지는 0으로 만들고, 0인 페이지는 victim으로 선정한 뒤 멈춘다
  • LRU가 비싸서 이렇게 사용

Translation Lookaside Buffer

• Motivation
  • 매번 MMU가 page translation을 위해 메인 메모리를 뒤져야 한다 → Overhead
  • 캐시를 이용해 page table entry를 저장해 두자
  • 
• 주로 Set-associative cache
  • 어차피 작아서 찾는 시간은 중요하지 않고 miss rate를 줄이는 것이 중요함
  • Associativity도 큰 편
• Micro-TLB
  • 메인 TLB의 캐시같은 것
  • 메인 TLB보다 더 작은 수의 엔트리를 가지고 있다

TLB Hit

1. CPU가 MMU에게 Virtual address의 변환을 요청
2. MMU가 Virtual page number로 TLB를 찾아봄
3. TLB hit ) TLB가 page table entry를 돌려줌
4. MMU는 이를 이용해 physical address를 찾아서 메인 메모리 접근
5. 데이터를 CPU에게 보내줌

TLB Miss

1. CPU가 MMU에게 Virtual address의 변환을 요청
2. MMU가 Virtual page number로 TLB를 찾아봄
3. TLB miss ) MMU는 PTE address로 직접 메인 메모리 접근
4. 메인 메모리의 PTE를 TLB에 업데이트
5. MMU는 physical address로 메인 메모리 접근
6. 데이터를 CPU에게 보내줌

Virtually addressed cache vs Physically addressed cache

• Virtually addressed cache
  • Address translation이 필요 없어서 빠르다
  • 보안 문제가 존재하여 컨텍스트 스위칭 시 OS의 개입이 필요하다
    • OS가 캐시를 flushing해주지 않으면 실수로 다른 프로세스의 메모리 영역을 읽을 수 있음
• Physically addressed cache
  • Address translation이 필요해서 느리다
  • 보안 문제가 존재하지 않는다 (따라서 OS 개입이 필요 없다)

Virtually Indexed, Virtually Tagged

• Virtual address를 이용해 캐시 인덱스와 태그를 사용하는 것
• TLB(Address translation)가 critical path에 존재하지 않음
  • TLB 룩업할 필요가 없음
• Virtually addressed cache임 → 보안문제 존재

Virtually Indexed, Physically Tagged

• 실제로 많이 사용
• Cache index로 찾는 동안 TLB translation을 수행하여 latency를 숨기는 것
• Physically indexed cache보다 더 빠르고, 보안 문제도 없다

Physically Indexed, Virtually Tagged

• 사용되지 않음
• 성능문제
• TLB address translation이 critical path에 존재

Physically Indexed, Physically Tagged

• Physically addressed cache임 → 느림
• TLB address translation이 critical path에 존재

정리