[Lecture 18] Virtual Memory / 가상 메모리: Principles and Mechanisms

#컴퓨터 구조 리뷰

Virtual memory/가상 메모리에 대해 보기 앞서 기본 컴퓨터 구조 개념을 다시 한번 살펴보자.

• Virtual address / 가상 주소:
  • 링커, printf("%p\n", ptr) 등등과 같이 사용자 프로그램에서 사용하는 주소
  • 범위: 0~2^ addresswidth
• Physical address / 물리 주소
  • 내부적으로 메모리 주소를 지정하는 데 사용되는 주소. 사용자에게 보이지 않음
  • 범위: 0~X (여기서 X는 컴퓨터의 메모리이다)
• Page / 페이지
  • Virtual page: 인접한 가상 주소 범위
  • Physical page (frame): 인접한 물리적 주소 범위
• MMU (Memory management unit)
  • 페이지 테이블에서 찾은 정보를 기반으로 가상 페이지를 물리적 페이지에 매핑하는 메모리 관리 장치
  • TLB: (Translation Lookaside Buffer)
    • TLB는 이러한 매핑을 캐싱한다

#Virtual Memory

• 가상 메모리는 메모리의 "종류"가 아니다
• 다음 개념 중 하나 이상을 결합하는 "기법"이다
  • 주소 변환 (Address translation) (항상 실행)
  • 디스크에서/디스크로 페이징 (보통 실행함)
  • Protection (보통 실행함)
• 물리적 DRAM이 아닌 스토리지를 실제처럼 보이게 할 수 있다

#가상 메모리의 주요 목표

• Virtualization / 가상화
  • 가상화란 물리적 컴퓨팅 자원을 논리적으로 나누어 사용자에게 서로 다른 서버나 운영체제 등으로 보이게 하는 기술이다. 즉, 여기선 프로세스가 전체 메모리를 가지고 있다는 착각을 유지하는 것이 가상화이다
    • 프로세스당 주소 공간
  • 프로세스가 실제 시스템에 있는 것보다 더 많은 메모리에 액세스할 수 있도록 허용(또는 모든 프로세스가 사용하는 모든 메모리의 합 > 물리적 메모리)
    • DRAM을 디스크용 캐시로 만든다
• Protection
  • 프로세스가 의도치 않게 다른 프로세스의 데이터에 액세스할 수 없도록 하는 것을 protection이라고 한다
  • 시스템 내부 데이터/커널 데이터 보호

#Address Translation

주소 변환은 버퍼 메모리가 있는 컴퓨터에서 논리 주소를 실제 주소(real address)로 변환함과 동시에 논리 주소 또는 실제 주소를 버퍼 메모리 상의 실제 주소로 변환하는 것이다. 쉽게 말해 상대적 주소를 절대적 주소로, 또는 그 반대로 변환하는 것이다.

• OS가 메모리 액세스에 개입할 수 있는 방법을 제공한다
• OS가 각 프로세스에 대해 프로세스별 페이지 테이블에 {가상 주소} → {물리적 주소} 매핑을 유지 관리함
  • 어느 가상 주소가 유효한지 확인(프로세스 메모리 레이아웃에 따라 다름)
  • 매핑 위치 결정(물리적 메모리 가용성에 따라 다름)
  • 허용되는 액세스 유형 결정 (read/write/execute)
• OS가 페이지 테이블을 관리
  • 사용자 프로세스의 입력 또는 명령에 기반해 관리함
  • 리소스 관리 결정 기준에 의해 관리

#Address Translation & TLB

#주소 공간 전환

• 다음 사진들은 모드 switch/context switch/mode 스위치 시퀀스에서 virtual-to-physical 매핑이 어떻게 변경되는지 보여준다 (커널 수준 구현 세부 정보도 조금 보여준다)
• 멀티 스레드의 경우 컨텍스트 스위치가 현재 주소 공간의 변경을 포함할 수도 있고 포함하지 않을 수도 있다
• 주소 공간 전환 비용이 컨텍스트 전환 비용에 추가된다
  • 주로 기회 비용(opportunity cost): TLB를 플러시해야 하기 때문에 플러시 후 miss된 항목을 다시 채워야 한다

#Meltdown Mitigation

• Meltdown 후, 커널 및 사용자 모드가 더 이상 동일한 페이지 테이블을 사용하지 않음
• 따라서 프로세서가 커널 모드로 전환되면 (빨간색) 커널 매핑에 더 이상 즉시 액세스할 수 없다
• 커널을 입력한 후 추가 페이지 테이블 스위치가 필요하다(비싸다). 필요하지 않으면 동일한 설정을 유지한다

#디스크로/디스크에서 페이징

• 프로세스에서 실제로 액세스하는 데이터만 물리적 메모리에 저장
• 각 프로세스에 대한 맵 유지 관리 { 가상 주소 } → { 물리적 주소 } ∪ { 디스크 주소 }
• OS가 매핑을 관리하고 물리적 주소(할당된 경우)와 디스크에 매핑할 가상 주소를 결정한다
• 디스크 주소에는 다음이 포함된다
  • 실행 파일, .text, 초기화된 데이터
  • 스왑 공간(일반적으로 지연 할당됨)
  • 메모리 매핑(mmap'd) 파일
• 요구 페이징 (Demand paging): 프로그램의 실행중에 필요하게 된 시점에서 보조 기억 장치(auxiliary storage)로부터 주기억 장치로 페이지를 전송하는 것. 선행 페이징(anticipatory paging)과 대비된다. 처음 액세스할 때 디스크에서 데이터를 지연적으로 가져온다
  • 응용 프로그램에 알려지지 않음

#Process Memory 사진

OS는 각 프로세스의 주소 공간 구조를 유지한다. 즉, 유효한 주소, 무엇을 참조하는지, 심지어 현재 메인 메모리에 없는 주소도 유지한다

#Servicing Page Faults

• 프로세스가 현재 매핑되지 않은 주소에 액세스하면 하드웨어가 고장 신호를 보낸다
  • if(주소가 커널 공간에 있거나 매핑되지 않은 영역을 참조하는 경우)
    • 프로세스에 SIGSEGV 전송
  • else: 그렇지 않으면 어떤 지역 주소가 있는지 확인
    • if(힙인 경우 새 페이지("minor falut")를 할당하거나 디스크에서 페이지를 스왑)
    • if(코드 세그먼트인 경우 실행 파일에서 코드 읽기)
    • if(글로벌 변수에 처음 액세스하는 경우 디스크에서 데이터를 읽고), else: 그렇지 않으면 디스크에서 스왑
    • if(매핑된 파일에 액세스할 경우 파일에서 데이터 읽기)
  • 페이지 테이블에서 새 v-p 매핑을 설정하고 다시 시도
  • 메모리에 있는 페이지에 대한 페이지 fault는 존재 하지 않는다
  • TLB miss가 있을 수 있지만 x86에서는 하드웨어에서 처리되므로 숨겨진 성능 비용이 발생할 수 있다

#스택 증가(Stack Growth) 더 자세히 보기

#fork()/exec() 리뷰

• fork():
  • 상위 페이지 테이블 복제
  • 모든 항목  read-only로 설정
  • 쓰기 시 복사 수행(공유 중에 발생하는 경우)
• exec():
  • 모든 기존 페이지 테이블 항목 제거
    • 상위 항목 공유 해제
  • 실행 파일의 지침에 따라 다시 시작
• common case 최적화: 자식 프로세스는 fork() 직후에 exec()을 수행

#물리 메모리 관리

• OS는 물리적 메모리를 사용할 대상을 결정해야 함
  • 응용 프로그램 데이터
    • 공유 메모리 영역을 제외한 대부분 per process
    • Heaps, stacks, BSS (Block Started by Symbol)
  • 파일 데이터(파일당 단일 복사본)
    • Mmaped 파일, 실행 파일, 공유 lib
    • 명시적 I/O를 통해 최근에 액세스한 파일 chunk
• 수요가 공급보다 클 경우 디스크로 페이지를 "제거 (evicting)"하여 물리적 메모리를 다시 지정해야 한다
  • 이 과정은 약간의 히스테리시스로 미리 완료된다
  • 또는 마지막에 완료된다 (“direct reclaim”)

#페이지 교체 전략

• 예측 게임과 비슷하다: 최적의 전략은 미래에 가장 멀리 데이터에 액세스할 페이지를 대체("제거")하는 것이다
  • 물론, 그건 알 수 없다. 휴리스틱(heuristics)을 사용해 한다
• 대부분의 휴리스틱은 "과거 = 미래" 아이디어와 대략적인 LRU를 기반으로 한다
  • 대규모 루프 액세스 또는 단일 순차 읽기와 같이 LRU가 실패하는 것으로 알려진 시나리오에 대한 가드를 추가하는 동안
  • LRU 목록의 액세스당 유지보수 비용이 너무 많이 들기 때문에 대략적으로 계산해야 한다
• 파일 데이터 대 프로세스 데이터의 무게를 측정해야 함
• 동일한 프로세스의 다른 페이지와 모든 프로세스의 페이지를 비교 검토해야 함
  • 로컬 대 글로벌 교체 policy

#VM Access Time & Page Fault Rate

access time = p * memory access time + (1-p) * (page fault service time + memory access time)

• 페이지 fault를 유발하지 않는 페이지 액세스의 p 부분에 대해 예상 액세스 시간을 고려해야 한다
• 그러면 1-p는 페이지 fault 빈도이다.
• p = 0.99, 메모리가 100ns 빠르며 페이지 fault servicing에 10ms가 걸린다고 가정하자. 물리적 메모리에 비해 VM 시스템 속도가 얼마나 느릴까?
• access time = 99ns + 0.01*(10000100) ns ≈ 100,000ns 또는 0.1ms이다
  • 100ns 또는 0.0001ms 속도와 비교 해보면 약 1000배의 속도 저하이다
• 결론: 상대적으로 낮은 페이지 fault rate도 큰 속도 저하로 이어진다. 페이지 fault rate를 매우 낮게 유지해야 한다.

#Thrashing

가상 기억 장치 시스템에서, 프로그램이 접근한 페이지나 세그먼트를 디스크에서 주기억 장치로 올려놓기 위한 페이지 틀림이 너무 자주 일어나 프로그램의 처리 속도가 급격히 떨어지는 상태. 시스템이 처리할 수 있는 것보다 더 많은 작업을 무리하게 실행시키려 할 때 발생한다.

스래싱 문제로 인한 멀티프로그래밍 효율 저하 현상

• VM은 작업 설정 크기(관심 있는 시간 범위 내에 액세스하는 메모리 양)를 물리적 메모리에 수용할 수 있는 경우 잘 작동한다
• 작업 세트 크기가 너무 커지면 OS가 페이지 장애를 지속적으로 처리하고 액세스한 페이지를 즉시 제거("evict")한다
• “thrashing”의 결과
  • 계산에 진전이 없는 상태에서 지속적으로 디스크로 데이터 이동/디스크에서 데이터 이동
  • 낮은 CPU 활용률로 이어짐

#Prefetching

선반입 (prefetching)은 CPU가 앞으로 수행될 명령어를 메모리에서 미리 인출하여 CPU 내부의 큐에 넣어 둠으로써 수행속도를 향상시키는 기법이다.

• 모든 최신 VM 시스템에서 프리페칭을 사용한다
  • 일반 전략: 파일에 대한 순차적 액세스 탐지
    • 가상 메모리 시스템 및 매핑된 파일을 통해 수행되는 경우에도
  • 때때로 application-guided
    • Linux readahead(2) 시스템 콜
    • 예: Windows Vista는 응용 프로그램이 터치한 데이터를 기억한다(시작 시간 단축)
    • VM 시스템의 성능은 페이지 교체 및 프리페치 전략에 따라 달라진다

#Using mmap()

mmap(2)은 파일이나 장치를 메모리에 매핑하는 POSIX 호환 유닉스 시스템 호출이다. 쉽게 말해 프로세스가 주소 공간에 매핑을 만들 수 있는 Unix API이다.

//int prot는 PROT_READ, PROT_WRITE, PROT_EXEC
//int flags는 MAP_SHARED, MAP_PRIVATE, MAP_ANONYMOUS, MAP_FIXED
void *mmap(void *start, size_t length, int prot, int flags,int fd, off_t offset);
int munmap(void *start, size_t length);

#파일 I/O를 위한 mmap()

int
main(int ac, char *av[])
{
    int fd = open(av[1], O_RDONLY);
    assert (fd != -1);
    
    off_t filesize = lseek(fd, 0, SEEK_END);
    assert (filesize != (off_t) -1);
    
    size_t pgsize = getpagesize();
    size_t mapsize = (filesize + pgsize - 1) & ~(pgsize-1);
    
    void *addr = mmap(NULL, mapsize, PROT_READ, MAP_PRIVATE, fd, 0);
    if (addr == MAP_FAILED) {
    perror("mmap"); exit(-1);
    }
    assert (close(fd) == 0);
    
    //메모리처럼 파일데이터 액세스
    char *start = addr, *end = addr + filesize;
    while (start < end)
    	fputc(*start++, stdout);
    return 0;
}

#parent/child communication을 위한 mmap()

int
    main(int ac, char *av[])
    {
    size_t sz = getpagesize();
    int sharedflag = ac < 2 || strcmp(av[1], "-private") ? MAP_SHARED : MAP_PRIVATE;
    void *addr = mmap(NULL, sz, PROT_READ|PROT_WRITE, MAP_ANONYMOUS | sharedflag, -1, 0);
    assert (addr != MAP_FAILED);
    printf("Memory mapped at %p\n", addr);
    
    int i, *ia = addr;
    if (fork() == 0) {
    for (i = 0; i < 10; i++)
   	 ia[i] = i;
    } else {
    assert (wait(NULL) > 0);
    for (i = 0; i < 10; i++)
    	printf("%d ", ia[i]);
    printf("\n");
    }
    return 0;
}

#mmap() & shared semaphores

int main(int ac, char *av[]){
    size_t sz = getpagesize();
    int sharedflag = ac < 2 || strcmp(av[1], "-private") ? MAP_SHARED : MAP_PRIVATE;
    void *addr = mmap(NULL, sz, PROT_READ|PROT_WRITE, MAP_ANONYMOUS | sharedflag, -1, 0);
    
    assert (addr != MAP_FAILED);
    sem_t *semp = (sem_t*) addr;
    assert(sem_init(semp, /* shared */1, /* initial value */ 0) == 0);
    
    int i, *ia = addr + sizeof(*semp);
    if (fork() == 0) {
        for (i = 0; i < 10; i++)
       		ia[i] = i;
        sem_post(semp);
    } else {
    sem_wait(semp);
    for (i = 0; i < 10; i++)
    	printf("%d ", ia[i]);
    printf("\n");
    }
    return 0;
}

#mmap() & persistent variables (1)

#define PGSIZE 4096

char persistent_data[PGSIZE] __attribute__((aligned(PGSIZE)));

int
main(int ac, char *av[])
{
    int i, do_read = ac < 2 || strcmp(av[1], "-read") == 0;
    persist(".persistent_data", persistent_data, sizeof (persistent_data));
    
    if (do_read) {
    	for (i = 0; persistent_data[i] != 0 && i < PGSIZE; i++)
    		fputc(persistent_data[i], stdout);
    } else {
    int c;
    for (i = 0; i < PGSIZE && (c = fgetc(stdin)) != -1; i++)
    	persistent_data[i] = c;
    memset(persistent_data + i, 0, PGSIZE - i); // zero rest
    }
    return 0;
}

#mmap() & persistent variables (2)

/*
* 크기가 'size'인 변수 'variable addr'을 파일 'filename'에서 persistent로 만들기
*/
static void
persist(const char *filename, void *variableaddr, size_t size){
assert (size % getpagesize() == 0);
int fd = open(filename, O_RDWR | O_CREAT, 0666);
assert (fd != -1);
assert (ftruncate(fd, size) == 0);
void *addr = mmap(variableaddr, size,PROT_READ | PROT_WRITE, MAP_FIXED | MAP_SHARED, fd, 0);
assert (addr == variableaddr);
assert (close(fd) == 0);
}

#요약

• 가상 메모리는 다음을 결합하는 기술이다
  • 주소 변환 / Address translation (Indirection)
  • 요구 페이징 / Demand paging
  • Protection

물리적 메모리를 가상화하고 애플리케이션과 커널을 보호한다. 성능에 영향을 미칠 수 있는 경우를 제외하고는 애플리케이션에 투명하다