Memory Management1

Contents

• 주소 공간 (Address Space)
• 물리 주소와 가상 주소(PA and VA)
• 가상 메모리
• Paging
• Translation Look-aside Buffers(TLB)
• 다양한 paging table

서론

• 범용 컴퓨터 시스템의 목적
  • CPU의 활용률을 극대화(utilization)
  • 사용자에게 빠른 응답을 제공
    • 보다 많은 프로그램을 메모리에 올려서 실행시킴 (multi-programming)
    • 여러 프로그램을 동시에 실행시키기 위한 스케줄링 기법 등장
• 메모리 관리의 필요성 등장
  • 여러 프로그램이 동시에 메모리에 적재되어 실행되면서, 메모리를 공유할 필요가 생김
  • 컴퓨터의 메모리는 한정된 자원
    • 실행하는 프로그램이 많아지면 메모리의 요구량이 증가

주소 공간

• 정의(address space)
  • 프로세스에서 참조할 수 있는 주소들의 범위(집합)
  • 프로세스와 1-1의 관계
  • 사용자 쓰레드는 주소 공간을 공유함
• 주소 공간의 크기
  • CPU의 주소 버스(address bus)의 크기에 의해 의존
  • 주소 버스가 32bit인 시스템에서 주소 공간의 크기
    • 2^32^개의 서로 다른 주소에 대한 식별자를 만들 수 있으므로
    • 0부터 (2^32^-1)까지의 주소 범위를 addressing할 수 있다.
  • 32bit 주소 버스를 가진 시스템이 주소 1개당 1Byte의 메모리를 접근할 수 있다면, 이 시스템이 address할 수 있는 주소 공간의 크기는 몇 Byte인가?
    • 32GB

물리 주소와 가상 주소

• 물리 주소 (physical address)
  • 컴퓨터의 물리 메모리를 접근할 때 사용되는 주소
• 가상 주소 (virtual address)
  • 물리 주소가 아닌 주소
    • 프로세스는 가상 주소 사용
      • CPU 관점에서 주소는 물리 주소도, 가상 주소도 될 수 있음
  • 가상 주소는 필요에 따라 의미를 달리하며 생성됨
    • 가상머신에서 사용되는 가상 주소는 복잡도가 더해짐
    • Intel은 주소 공간을 segment 단위로 나누어 사용

단계별로 다른 형태의 주소가 생성됨

Compile time 주소

• 초창기에는 compile time에 물리 주소를 생성

  • 컴파일러가 물리 메모리에서 실행되는 주소에 대해서 알아서 물리 주소를 생성한다.

  • 1개의 프로그램이 실행될 경우 문제가 없음

  • 시작 주소의 위치가 바뀔 경우에는 다시 compile을 해야 한다.

    예) DOS binary format

• 그러나, 다중 프로그램이 실행됨에 따라 compile time에 물리 주소를 정하기가 어려워짐

  • Multiprogramming의 경우, compile time시에 결정된 주소는 다른 프로그램과 같이 메모리에 적재하기 어려움
    • 가상 주소를 생성하기 시작함

Compile 및 Link에서의 주소

• Compile time
  • Compiler가 symbol table을 만들고 주소는 symbol table relative한 주소로 이뤄짐
  • 컴파일된 object 파일은 주소 0부터 시작함(relocatable)
• Link time
  • Object 파일들과 library들을 묶어서 symbol table에 의존적이 아닌 주소를 만들어 냄(address resolution)
  • Link의 결과로 하나의 executable 파일이 만들어지고 시작 주소는 0부터 시작함
  • 이 executable에서 프로세스가 만들어질 때, 주소 공간이 만들어짐

물리 주소 결정: Load 또는 실행시

• Load time
  • 프로그램의 실행을 위해 loader는 executable을 메모리로 load한다.
  • 주소 공간 전체가 메모리에 올라간다면, load시에 물리 주소에 대한 binding이 일어난다.
    • executable은 relocatable 주소로 되어있기 때문에 base register(relocation register)를 통해서 물리 주소로 변환함
      • symbol table relative + base register = physical address
    • 가상 주소에 물리 주소가 mapping됨
• Execution time
  • 프로세스가 실행될 때 물리 주소를 바꾸는 것이 가능함
    • Paging을 통해서 가상 주소의 mapping이 바뀌게 됨
  • 이러한 형태의 주소 결정 방법을 사용하기 위해서 MMU와 같은 특별한 하드웨어가 필요하게 된다.
    • 특별한 하드웨어는 성능 때문에 필요
  • 최신 general-purpose 운영체제에서는 이 방식을 사용

mapping의 조건

• 가상 주소(x)에 대해서 물리 주소(y) 하나가 mapping
• 하나의 가상 주소에 대해서 하나의 물리 주소만 mapping 가능
• 하나의 물리 주소에 대해서 여러 개의 가상 주소 mapping 가능
• 함수의 조건과 유사

Load할 때 주소 변환 방법

• 컴퓨팅 초기에
  • 멀티프로그래밍(만) 지원
  • Executable 주소를 relocation register의 값과 더한 값이 물리 주소가 됨
  • Relocation register의 값을 바꿈으로 executable의 물리 주소를 바꿀 수 있음

• 346이라는 가상 주소가 relocation register인 14000이 더해짐으로써 14346이라는 물리주소로 mapping되는 것을 의미
• 여기서 346이라는 가상 주소는 CPU가 보는 주소로 이것만 갖고는 CPU가 물리주소에 도달하지 못한다. 따라서 별도의 mapping이 필요하다.

주소 변환 모델

• Translation == Mapping

• 프로세스가 수행할 때

  • Virtual address를 생성

• Translation의 속도가 전체 성능에 중요한 요소가 된다.
  • 모든 instruction마다 translation이 발생하기 때문

Memory Management Unit(MMU)

• Virtual address와 Physical address 간의 변환을 수행하는 hardware 장치

MMU가 번역한 물리 주소에 대한 캐시는 CPU의 어디에 위치하는가?

MMU의 앞, 즉 MMU 보다 더 가까운 위치에 존재하여 캐시를 거쳐서 MMU에 도달하게 한다. 그럼 캐시를 통해 인덱싱되는 주소들은 물리 주소의 형태로 저장될까? 가상 주소의 형태로 저장될까? 가상 주소로 접근되며, 이때 context switching마다 가상 주소가 바뀌기 때문에 캐시를 flush해줘야 한다. 현재는 L1은 MMU 앞에, L2는 MMU 뒤에 있다고 할 수 있다.

가상 메모리

• 정의
  • 실제 존재하지는 않지만 사용자에게 메모리로서의 역할을 하는 메모리(virtual)
• Basic Idea
  • 프로세스가 수행되기 위해서 프로그램의 모든 부분이 물리 메모리(Physical memory)에 있을 필요는 없다.
    • 현재 실행되고 있는 code/data/stack의 일부분만이(전체가 아니라) 물리 메모리에 있으면 프로세스는 실행 가능

가상 메모리 - main memory와 secondary storage를 이용한 구현

• 물리 메모리보다 큰 가상 메모리의 diagram
  • 물리 메모리보다 가상 메모리가 커지면 메모리 일부는 Secondary Storage, 즉 어떤 디스크에 저장한다.
  • 리눅스에서는 프로그램 개발을 할 때, swap space를 얼마로 설정할 지 정할 수가 있다. 이 swap space가 Secondary Storage이다. 다른 OS에서는 이 swap space를 알아서 계산해서 정해준다.
  • 안드로이드에서는 swap space를 어떻게 제어할까?
• 가상 메모리가 물리 메모리 + Secondary Storage를 다 더하고도 넘칠 정도로 커지면 그제서야 OS가 프로세스를 다운시킨다.

virtual to physical address mapping table

• virtual Page는 프로세스마다 정의가 된다. 따라서 shared memory에 따라 각각의 다른 프로세스가 같은 물리 주소를 가리키고 있더라도 두 개의 다른 가상 주소가 하나의 물리 주소를 가리킬 수 있기 때문에 자연스럽게 구현이 가능해진다.

Q : 쓰레드는 그럼 어떻게 주소 공간을 통해 물리 주소에 접근합니까? A : 한 프로세스에 있는 쓰레드들끼리는 같은 주소 공간을 공유하기 때문에 Page Table에 저장된 같은 정보를 통해서 물리 메모리를 접근할 수가 있게 된다.

물리 주소와 Secondary Storage는 별도의 테이블을 가진다. 따라서 가상 메모리와 물리 메모리를 연결해주는 mapping table과 물리 메모리와 Secondary Storage를 연결하는 메커니즘 또한 별도로 분리된 것이다.

Q : Address Space 테이블은 물리적으로 어디에 있나요? A : 메모리에 있으며 MMU는 그것에 대한 캐시를 갖고 있다. PCB에는 Virtual Page의 시작 위치가 들어있다.

Paging

• 주소 공간을 동일한 크기인 page로 나누어 관리
  • 보통 1page의 크기는 4KB로 나누어 사용
  • 프레임(Frame)
    • 물리 메모리를 고정된 크기로 나누었을 때, 하나의 블록
  • 페이지(Page)
    • 가상 메모리를 고정된 크기로 나누었을 때, 하나의 블록
  • 각각의 프레임 크기와 페이지 크기는 같다.
• 페이지가 하나의 프레임을 할당 받으면, 물리 메모리에 위치하게 된다.
  • 프레임을 할당 받지 못한 페이지들은 외부 저장장치(Backing store)에 저장된다.
    • Backing store도 페이지, 프레임과 같은 크기로 나누어져 있다.