Memory Virtualization 1 - 운영체제

Memory Virtualization (메모리 가상화)

• Virtual RAM: 각 프로세스가 Private Memory를 가지고 있는 것처럼 구현
• 메모리는 OS와 User Process 영역으로 나뉜다
• Uniprogramming:
  • 한 번에 하나의 프로세스만 돈다
  • 가상화를 지원하지 않음
  • 코드가 OS를 망칠 수도 (Protection이 없음)
• Multiprogramming Goal
  • Transparentcy
    • 모든 프로세스가 메모리가 공유된다는 사실을 모름
    • 실제 프로세스는 프로세스의 갯수, 위치에 상관없이 작동하여야 한다
  • Protection
    • 한 프로세스가 다른 프로세스나 OS의 영역을 침범할 수 없다
    • 다른 프로세스의 데이터를 읽지도 못함
  • Efficiency
    • 메모리 자원을 낭비하지 않아야 한다
    • Fragmentation(파편화)를 최소화하여야 한다
  • Sharing
    • Cooperating Process는 메모리 공간의 일부분을 공유할 수 있다

Abstraction

• Address Space: 각 프로세스는 바이트에 매핑되는 일련의 주소를 가짐
• 문제점: OS가 각 프로세스에 Private Address Space를 제공하는 것처럼 보여야함
• Address Spaced에 무엇이 있는가:
  • 코드: 코드와 글로벌 변수
  • 힙: 동적 할당 변수
  • 스택: 지역 변수

Motivation For Dynamic Memory

• 메모리의 dynamic allocation이 필요한 이유
  • 컴파일 시점에는 메모리 필요량을 알지 못하는 경우
  • 정적으로 메모리를 할당할 때는 반드시 낭비 없이 할당해야 함
• recursive procedure
  • 얼마나 많이 실행될 지 알 수 없음
• 복잡한 데이터 구조: 리스트, 트리
• 두 가지 동적 할당
  • 스택
  • 힙

스택 구성

• 할당한 순서의 반대로 메모리를 해제한다
• alloc(a) -> alloc(b) -> free(b) -> free(a)
• 간단하고 효율적인 구현
• 언제 사용하는가?
  • procedure call frame에 사용되어 로컬 변수와 파라미터가 stack의 형태로 할당됨

힙 구성

• 임의의 위치에 메모리 할당: malloc(), new()
• 힙 메모리는 할당된 공간과 free area로 구성 (holes)
• 할당 위치를 예측할 수 없다
• 이점:
  • 모든 데이터 구조에 사용 가능
• 문제점:
  • 할당이 느릴 수 있다
  • free space가 자료를 담기엔 너무 작은 공간만 남은 경우에는 내부 단편화
  • 할당해야 할 크기가 너무 크면 외부 단편화가 발생할 수 있다
• Heap 관리할 때 OS의 역할은 무엇인가?
  • OS는 big chunk of free memory를 프로세스에 제공
  • 라이브러리가 개개의 할당을 관리한다

Quiz: Address Location

int x;
int main(int argc, char *argv[]) {
    int y;
    int *z = malloc(sizeof(int));
}

x는 static data, main은 code, y는 stack, z는 stack, *z는 heap 영역에 존재한다

Quiz: Memory Access

0x10:    movl    0x8(%rbp), %edi
0x13:    addl    $0x3, %edi
0x19:    movl    %edi, 0x8(%rbp)

• initial %rip = 0x10

• %rbp = 0x200

• Fetch Inst at addr 0x10

• Exec:

  • load from addr 0x208

• Fetch Inst at addr 0x13

• Exec:

  • no mem access

• Fetch Inst at addr 0x19

• Exec:

  • store to addr 0x208

How to Virtualize Memory?

• 멀티 프로세스를 동시에 돌리려면
  • 만약 주소가 프로세스 바이너리 파일에 "hardcoded" 된 상태라면
    • 상대 주소가 달라져서 collision 발생
  • collision을 피하는 방법
    1. Time Sharing
    2. Static Relocation
    3. Base
    4. Base + Bounds
    5. Segmentation

1. Time Sharing (시분할 메모리)

• CPU 가상화와 비슷한 접근법
• 물리적인 메모리를 언제 얼마나 해당 프로그램이 사용할 지 결정
• OS가 현재 작동하지 않는 프로세스의 메모리를 memory를 disk에 저장하여 가상 메모리를 흉내
• 굉장히 비효율적
• 더 나은 대안: space sharing
  • 같은 시간에 메모리 공간이 프로세스마다 나뉘어있음

2. Space Sharing

• OS가 각 프로그램을 메모리에 올리기 전에 rewrite 한다
• 각 프로세스를 위한 rewrite는 다른 주소와 포인터를 사용한다
• static data의 jump, load를 수정한다
• stack의 주소를 변경하지 않는 이유:
  • 프로세스를 기준으로 상대적으로 위치를 잡기 때문에
• 문제는 Privacy, Protection을 위한 매커니즘이 없다는 것
• 일단 메모리에 올라가면 새로운 프로세스를 할당할 수 없다

3. Dynamic Relocation with Base Register

• 목표: Protection
• 하드웨어의 지원이 필요하다
  • Memory Management Unit(MMU)
• MMU는 매 메모리 reference마다 프로세스 주소를 다이나믹하게 바꾼다
  • logical -> physical, virtual -> real address로 변환
• 두 가지 실행 모드
  • Privileged (protected, kernel) mode: OS 실행
    • trap, syscall, interrupt, exception 등으로 OS 진입할 떄
    • 특정 명령어가 실행되도록 만든다
      • MMU Contents 조작할 수 있다
    • OS가 모든 Physical Memory 접근할 수 있게 허용한다
  • User Mode: 사용자 프로세스 실행
    • logical -> physical address 번역 실행
• Minimal MMU는 Base Register를 가지고 Translation 진행
  • base: address space의 시작 위치 저장
• 모드에 따라 user mode면 base를 더해 physical address 반환
• kernel mode면 그 자체가 phys addr
  

  

• Idea: 매번 base 오프셋 값을 virtual addr에 더해 phys addr 구한다
• base register에 offset 저장
• 각 프로세스는 base register 값이 다 다르다
• Base Register 값은 OS가 결정
• 문제점: P1이 P2를 접근하는 게 여전히 가능하다
  • 마지막 명령의 경우

4. Dynamic with Base + Bounds

• Base Register: 가장 작은 phys addr

• Bounds: 해당 프로세스의 virtual address space의 크기

  • 구현에 따라 (base + size) 값을 저장할 때도 있음

• 프로세스가 bound 너머에 접근하려 할 때 OS가 Kill
  

  

• Context-Switch

  • base와 bound를 PCB에 추가시킴
  1. Change to privileged mode
  2. save base, bounds registers of old process
  3. load base, bounds registers of new process
  4. change to user mode and jump to new process

• Protection Requirement

  • user process가 base, bounds register를 변경할 수 없음
  • user process가 privileged mode에서 실행될 수 없음

• 장점

  • protection (read/write 모두)
  • 다양한 공간에 프로세스를 할당할 수 있음
  • 간단하고 저렴한 비용으로 구현 가능
  • 더하기와 병렬적인 비교 연산만 필요하므로 빠르다

• 단점

  • 각 프로세스가 물리 메모리에서 연속적으로 할당되어야 한다
  • 하나의 프로세스는 하나의 거대한 메모리 공간을 잡아먹음 (사용되지 않아도)
  • partial sharing이 되지 않음: 메모리 공간의 일부를 공유할 수 없음

5. Segmentation

• 내부에 사용하지 않는 메모리 공간도 연속적인 할당에서 빼먹을 수 없음
  • 내부 단편화
• 프로세스가 필요로 하는 크기가 물리 메모리보다 큰 경우
  • 외부 단편화
• 이를 해결하기 위해선 비연속적으로 주소 공간을 할당할 수 있어야 한다
• Segment 당 Base, Bounds를 가져보자!
• 각 세그먼트는 연속적, 세그먼트끼리는 연속적이지 않음
• Code (Data), Stack, Heap
• Segmentation이 OS가 각 세그먼트를 서로 다른 물리 메모리 공간에 할당할 수 있게 해줌
• 각 세그먼트는 독립적임
  • 물리 메모리에 독립적으로 존재 가능
  • 늘어나고 줄어날 수 있다
  • 보호될 수 있다 (각각이 read/write/execute protection bits를 가짐)
• 프로세스가 세그먼트 별로 오프셋을 구분
• process가 특정 세그먼트 구분하는 방법
  • logical address의 일부를 사용한다
    • top bits는 세그먼트 선택을 위해 사용
    • low bits는 세그먼트 내에서 사용되는 오프셋이다

• MMU Segment Table
  • Base와 Bounds에는 물리적인 주소가 저장된다
  • seg 0는 read only
  • seg 1은 read/write
  • seg 2는 read/write
  • seg 3은 invalid 권한이다

• Example: 14 bit logical address
  • 0x1108 = 0001 0001 0000 1000b
  • 상위 2비트 01은 seg 1을 의미
  • 나머지는 Segment 내에서 위치를 잡기 위한 Offset
• 0x0240
  • 0000 0010 0100 0000b
  • seg 0, phys 0x2240, read only
• 0x1108
  • 0001 0001 0000 1000b
  • seg 1, phys 0x0108, read/write
• 0x265c
  • 0010 0110 0101 1100b
  • seg 2, phys 0x365c, read/write
• 0x3002
  • 0011 0000 0000 0010b
  • seg 3, phys 0x0002 (bounds error)

Segmentation의 장점

• 주소 공간을 부분적으로 할당할 수 있음
  • 각각 독립적으로 stack과 heap이 자라날 수 있다
  • Heap: free list에 데이터가 없으면 Dynamic Memory Allocator가 OS에 더 많은 메모리를 요청한다
  • Stack: OS가 즉시 스택을 확장한다
• 세그멘트마다 각기 다른 보호 정책을 설정할 수 있다
  • read only, write only, ...
• 선택된 세그먼트 간 주소 영역 공유 가능
• 각 세그먼트의 Dynamic Relocation을 지원

Segmentation의 단점

• 각 세그먼트는 반드시 연속적으로 할당된다
  • 여전히 내,외부 단편화 문제가 있다
• paging으로 개선 가능