[운영체제] 물리 메모리

메모리는 주소를 통해 접근한다.

• 논리적 주소(logical address 또는 virtual address)
  • 프로세스마다 독립적으로 가지는 주소 공간
  • 각 프로세스마다 0번지부터 시작
  • CPU가 보는 주소는 logical address임
    • 프로그램이 실행되서 메모리에 올라가더라도, 실행 파일의 instruction 내부의 logical address는 바뀌지 않음. 즉, CPU가 읽어들이는 instruction 내부의 주소는 logical address.
• 물리적 주소(physical address)
  • 메모리에 실제 올라가는 위치

주소 바인딩: 주소를 결정하는 것
symbolic address: 변수명 (컴파일되면 logical address로 바뀜)

symbolic address ---(컴파일)---> logical address ---(실행 시작)---> physical address

컴파일

소스코드가 컴파일이 되면 실행파일이 만들어지는데, 이 때 각 프로그램의 실행파일은 0번지부터 시작된다. 그리고 각 instruction과 symbolic address(=변수명)에 대응하는 logical address가 binding된다.

프로그램이 실행이 되려면 physical address가 결정되어야 함
그렇다면 physical address로의 변환은 언제 이루어지는가?

실행 시작 (물리적 메모리주소가 결정되는 시점에 따라 구분)

• Compile time binding

  • 물리적 메모리 주소(physical address)가 컴파일 시 알려짐 (논리적 주소가 사실상 물리적 메모리 주소임. 컴퓨터 안에서 프로그램이 하나만 실행되었던 과거 환경에서 사용되었음.)
  • 시작 위치 변경 시 재컴파일
  • 컴파일러는 절대 코드(absolute 코드) 생성 (절대코드가 실행 후 물리주소가 된다.)

• Load time binding

  • 물리 메모리 상에서 비어있는 공간에 프로그램을 적재하여 실행하는 시점에 물리적 메모리주소가 결정됨.
  • loader의 책임 하에 물리적 메모리 주소 부여
  • 컴파일러가 재배치 가능 코드(relocatable 코드)를 생성한 경우 가능 (재배치 가능 코드가 실행 후 물리주소가 된다.)

• Execution time binding (= Run time binding)

  • 수행이 시작된 이후에도 프로세스의 메모리 상 위치를 옮길 수 있음 (ex. swap in, swap out)

  • CPU가 주소를 참조할 때마다 binding을 점검. 주소 변환을 그 때 그 때 해야 함. (address mapping table)

  • 하드웨어적인 지원이 필요
    (e.g., base and limit register, MMU)

  • MMU(Memory Management Unit)
    logical address를 physical address로 매핑해주는 하드웨어 장치.

    • MMU scheme

      • 사용자 프로세스가 CPU에서 수행되며 생성해내는 모든 주소값에 대해 base register(=relocation register. 접근할 수 있는 물리적 메모리 주소의 최소값)의 값을 더한다.

      • CPU가 logical address x번지의 값을 요구 -> limit register값보다 작은지 확인. limit register보다 큰 값을 요구하면 trap: addressing error 발생(CPU 제어권이 운영체제로 넘어감.). -> relocation register를 더해서 물리 메모리 주소로 변환. -> 물리 메모리에서 CPU가 요구한 값을 읽어서 가져옴.

        • limit register: 논리적 주소의 범위. 악의적으로 CPU instruction을 통해 프로그램의 최대 크기를 넘어서는 메모리 주소 값을 달라고 명령하면 다른 프로세스 메모리 위치에 접근하는 것이 가능해져버리는 것을 방지.

      • ex) 프로그램의 최대 크기가 3000인데 4000번지의 값을 달라고 하면 악의적인 명령이므로 실행을 중지시켜야 함. -> trap: addressing error

      • ex) CPU가 346번지 값을 달라고 하면? logical address를 의미, 물리 메모리 주소로 변환 필요 -> relocation register(물리메모리에서 해당 프로세스의 시작 위치)의 값 14000을 논리주소 346에 더한다. -> CPU에게 14346번지 값을 전달.

  • user program

    • logical address만을 다룬다.
    • 실제 physical address를 볼 수 없으며 알 필요가 없다.

용어 설명

dynamic loading

loading: 메모리로 올리는 것.
프로세스 전체를 메모리에 미리 다 올리는 것이 아니라 해당 루틴이 불려질 때 메모리에 load하는 것. 특히 방어적 프로그래밍의 경우 프로그램에서 자주 사용되는 부분은 한정적임.
memory utilization 향상.
가끔씩 사용되는 많은 양의 코드의 경우 유용

• ex) 오류 처리 루틴
  운영체제의 특별한 지원 없이 프로그램 자체에서 (개발자가 명시적으로) 구현 가능 (OS는 라이브러리를 통해 지원 가능)

overlays

메모리에 프로세스의 부분 중 실제 필요한 정보만을 올림.
프로세스의 크기가 메모리보다 클 때 유용.
운영체제의 지원 없이 사용자에 의해 구현.
dynamic loading과 비슷한 개념이지만 역사적으로 다름. 작은 공간의 메모리를 사용하던 초창기 시스템에서 수작업으로 프로그래머가 구현 (manual overlay)
프로그래밍이 매우 복잡하다.

swapping

프로세스를 일시적으로 메모리에서 backing store로 쫓아내는 것.
backing store(=swap area): 디스크. 많은 사용자의 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장 공간.

• swap out: 메모리에서 backing store로 쫓겨나는 것
• swap in: backing store에서 메모리로 다시 올라오는 것

일반적으로 중기 스케줄러(swapper)에 의해 swap out 시킬 프로세스 선정.

priority-based CPU 스케줄링 알고리즘

• priority가 낮은 프로세스를 swap out 시킴
• priority가 높은 프로세스를 메모리에 올려 놓음.

compile time binding이나 load time binding에서는 원래 메모리 위치로 swap in해야 함. -> swapping이 효율적으로 동작하지 못함.
execution time binding에서는 추후 빈 메모리 영역 아무 곳에서나 올릴 수 있음.
swap time은 대부분 transfer time(swap되는 양에 비례하는 시간)임

(페이징 시스템에서는 프로그램 전체가 쫓겨나는게 아니라 일부 페이지가 쫓겨나는 개념으로 쓰기도 함. 원칙적으로는 프로그램을 구성하는 주소 공간이 전부 쫓겨나는 것임)

Dynamic Linking

Linking: 여러 군데에 존재하는 컴파일된 파일들을 하나로 묶어 실행 파일을 만드는 과정.
소스 파일을 여러개 따로 코딩을 해서 링킹하거나, 남이 만든 함수 또는 라이브러리를 불러다가 내 코드에 링킹하기도 함.

• static linking
  라이브러리가 프로그램의 실행 파일 코드에 포함됨.
  실행 파일의 크기가 커짐
  동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로 메모리 낭비 (eg. printf 함수의 라이브러리 코드)
• dynamic linking
  라이브러리가 실행 시 연결됨 (Linking을 실행 시간까지 미룸)
  라이브러리 호출 부분에 메모리에서 라이브러리 루틴의 위치를 찾기 위한 stub이라는 작은 코드를 둠 (라이브러리 자체는 실행 파일에 포함되지 않음)
  라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고, 없으면 디스크에서 읽어옴
  운영체제의 도움이 필요.
  dynamic linking해주는 라이브러리: shared library라고 부른다. (linux에서는 shared object, window에서는 DLL)

물리 메모리 할당

메모리는 일반적으로 두 영역으로 나뉘어 사용

• OS 상주 영역
  • interrupt vector와 함께 낮은 주소 영역 사용
• 사용자 프로세스 영역
  • 높은 주소 영역 사용

사용자 프로세스 영역의 할당 방법

연속 할당(Contiguous allocation)

각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것. 주소 변환이 간단하다.

고정 분할 방식(Fixed partition allocation): 물리적 메모리를 몇 개의 영구적 분할(partition)로 나눔

- 분할의 크기가 모두 동일한 방식과 서로 다른 방식이 존재
- 분할당 하나의 프로그램 적재
- 융통성이 없음
  - 동시에 메모리에 load되는 프로그램의 수가 고정됨
  - 최대 수행 가능 프로그램 크기 제한
- 내부 단편화 발생 (외부 단편화도 발생)

• 외부 조각: 프로그램 크기보다 분할의 크기가 작은 경우
  • 아무 프로그램에도 배정되지 않은 빈 곳인데도 프로그램이 올라갈 수 없는 작은 분할
• 내부 조각: 프로그램 크기보다 분할의 크기가 큰 경우
  • 하나의 분할 내부에서 발생하는 사용되지 않는 메모리 조각
  • 특정 프로그램에 배정되었지만 사용되지 않는 공간

가변 분할 방식(variable partition allocation):

- 프로그램의 크기를 고려해서 할당
- 분할의 크기, 개수가 동적으로 변함
- 기술적 관리 기법 필요
- 외부 단편화 발생
- Hole:가용 메모리 공간. 다양한 크기의 hole들이 메모리 여러 곳에 흩어져 있음. 프로세스가 도착하면 수용가능한 hole을 할당. 운영체제는 (a)할당 공간 (b)가용 공간(hole)의 정보를 유지한다.

dynamic storage allocation problem
: 가변 분할 방식에서 size n인 요청을 만족하는 가장 적절한 hole을 찾는 문제

• First Fit
  size가 n 이상인 것 중 최초로 찾아지는 hole에 할당
• Best fit
  size가 n 이상인 가장 작은 hole을 찾아서 할당
  hole들의 리스트가 크기 순으로 정렬되지 않은 경우 모든 hole의 리스트를 탐색해야 함
  많은 수의 아주 작은 hole들이 생성됨
• worst fit
  가장 큰 hole에 할당
  역시 모든 리스트를 탐색해야 함
  상대적으로 아주 큰 hole들이 생성됨
  -> First fit과 best fit이 worst fit보다 속도와 공간 이용률 측면에서 효과적인 것으로 알려짐 (실험적인 결과)

compaction

• 외부 단편화 문제를 해결하는 한 가지 방법
• 사용 중인 메모리 영역을 한 군데로 몰고 hole들을 다른 한 곳으로 몰아 큰 block을 만드는 것
• 매우 비용이 많이 드는 방법임
• 최소한의 메모리 이동으로 compaction하는 방법은 매우 복잡한 문제이다.
• runtime binding이 지원되어야 가능하다. (프로세스의 주소가 실행시간에 동적으로 재배치 가능한 경우에만 수행될 수 있다.)

불연속 할당(Noncontiguous allocation)

partition이 없음. 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있음.

Paging

• 프로세스의 가상 메모리를 동일한 사이즈의 페이지 단위로 나눔

• 가상 메모리의 내용이 페이지 단위로 불연속적으로 저장됨

• 일부는 backing storage에, 일부는 물리 메모리에 저장

• 외부 단편화 발생 안함, 내부 단편화 발생 가능

  basic method
  - 물리 메모리를 동일한 크기의 frame으로 나눔
  - 가상 메모리를 동일 크기의 페이지로 나눔 (frame과 같은 크기)
  - 모든 가용 frame들을 관리
  - page table(페이지들이 물리 메모리 어떤 frame에 올라가 있는지 entry 형태로 관리, n번째 페이지는 n번째 entry를 참조하면 몇 번째 page frame에 올라가 있는지 확인 가능)을 사용하여 logical address를 physical address로 변환
  

• page table의 구현

  • 프로그램마다 페이지 테이블이 별도로 존재하므로 용량이 매우 크다. -> 캐시나 레지스터에 들어가기에 용량이 너무 크므로, 메인 메모리에 상주.

  • 모든 메모리 접근 연산에는 2번의 메모리 access 필요 (page table 1번, 실제 데이터/instruction이 있는 곳 1번)
    - Page-table base register(PTBR)가 page table을 가리킴.
    - Page-table length register(PTLR)가 테이블 크기를 보관.

  • 속도 향상을 위해 associative register 또는 translation look-aside buffer(TLB)라 불리는 고속의 lookup hardware cache 사용. 메인 메모리와 CPU 사이에 존재. 주소 변환을 위한 캐시 메모리.

    • CPU가 논리적인 주소를 주면 페이지 테이블 접근 전에 TLB를 먼저 싹 다 병렬적으로 검색(parallel search). TLB에 저장되어 있는 정보로 주소 변환 가능?
      -> TLB hit (메인 메모리에 2번 접근할 필요할 필요가 없음.) page #이 TLB에 보관되어 있으면 곧바로 frame #을 얻음
      -> TLB miss (page table 통해서 주소 접근해야 함.) main memory에 있는 page table로부터 frame #을 얻음
    • TLB는 프로세스 별로 정보가 다르므로 context switch 때 flush. (old entries를 제거)
    • Effective acceess time

    Associate register look up time = ε
    memory cycle time = 1
    Hit ratio = α (associative register에서 찾아지는 비율)
    
    EAT = (1 + ε)α + (2 + ε)(1 - α) // TLB miss이면 메인 메모리에 2번 접근하므로
        = 2 + ε - α