주소 바인딩

메모리는 주소가 매겨지는데 크게 두가지로 나눌 수 있다

• 논리적 주소(Logical address = virtual address)

  • 프로세스마다 독립적으로 가지는 주소 공간
  • 각 프로세스마다 0번지부터 시작
  • CPU가 보는 주소는 logical address임

• 물리적 주소(physical address)

  • 메모리에 실제 올라가는 위치

주소 바인딩 : 주소를 결정 하는 것
Symbolic Address -> Logical Address -> Physical Address
논리적 주소에서 물리적 주소로 결정되는 시점이 언제인가?
Symbolic Address : 프로그래머 입장에선 숫자가 아닌 심볼로 된 주소를 사용한다

• Complie time binding
  • 물리적 메모리 주소(physical address)가 컴파일 시 결정된다
  • 시작 위치 변경 시 재컴파일
  • 컴파일러는 절대코드(absolute code)생성

    컴파일 타임 시점에서 만들어진 코드를 절대코드라고 부른다

  • 지금은 많이 사용하지 않지만 프로그램을 하나만 사용하던 시대에선 사용되기도 했다
• Load time binding
  • Loader의 책임하에 물리적 메모리 주소 부여
  • 컴파일러가 재배치 가능 코드(relocatable code)를 생성한 경우 가능
• Execution time binding(=Run time binding)
  • 수행이 시작된 이후에도 프로세스의 메모리 상 위치를 옮길 수 있음
  • CPU가 주소를 참조할 때마다 binding을 점검(address maapping table)
  • 하드웨어적인 지원이 필요(base and limit register, MMU)
  • 로드타임과 똑같이 물레적 메모리 주소가 결정되지만 실행 도중에 주소가 바뀔 수 있다.

물리적 메모리에 주소가 결정되는 것을 주소 바인딩이라고 부른다

CPU가 바라보는 주소는 뭘까? 하드웨어이기 때문에 물리적을 바라볼 것 같지만 논리 주소를 바라보고있아

런타임 바인딩 부터는 그때그때 내용이 어디에 올라가있는지 주소 변환을 새로해줘야하는데 하드웨어가 필요하다

Memory-Management Unit(MMU)

주소 변환을 위한 하드웨어
레지스터 두개를 통해 주소 변환을 하게 된다(relocation register, limit register)
logical address를 physical address로 매핑해주는 hardware device

• MMU scheme

  • 사용자가 프로세스가 CPU에서 수행되며 생성해내는 모든 주소값에 대해 base register(=relocation register)의 값을 더한다

• user programm

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

주소변환은 어떻게 되는가?
시작 위치가 14000번이고 논리주소가 346이다. 둘을 더하면 된다.
MMU에선 시작위치를 저장한다. 주소를 변환할 때는 시작위치에서 논리 주소를 더해서 물리적인 주소 위치를 얻게된다
limit register는 프로그램의 최대 크기가 있는데. p1의 경우는 3000이 최대 크기이다
limit register는 그 크기를 담고 있다.
만약 악성프로그램이 잘못된 논리 주소를 달라하면 잘못된 주소 변환이 되기 때문에 악의적인 프로그램이라 생각해서 막아야한다.

limit register의 값을 벗어나는 요청이면 트랩에 걸리게 된다
trap에 걸리면 이 프로그램이 CPU를 잡고 있었지만 하던 일을 멈추고 CPU 제어권이 운영체제로 넘어가게 된다
그럼 운영체제는 trap이 왜 걸렸는지(소프트웨어 인터럽트) 따져봐서 악의적이라 판단하면 강제 종료 시키거나 하는 작업을 하게된다
하지만 논리 주소가 limit register 이내의 범위라면 base register의 값을 더해 주소 변환을 한 후 물리적 메모리 어딘가에 있는 내용을 읽어 CPU에 전달해준다

Dynamic Loading(동적 로딩)

• 프로세스 전체를 메모리에 미리 다 올리는 것이 아니라 해당 루틴이 불려질 때(필요할 때) 메모리에 load하는 것
• memory utilization의 향상
• 가끔씩 사용되는 많은 양의 코드의 경우 유용
  • 예 : 오류 처리 루틴
• 운영체제의 특별한 지원 없이 프로그램 자체에서 구현 가능(OS는 라이브러리를 통해 지원 가능)

Loading? 메모리로 올리는 것

다이나믹 로딩은 운영체제가 하는 것이 아니라 프로그래머가 하도록 만드는 개념이다.
쉽게하도록 운영체제가 라이브러리 형태로 제공해준다. 일일이 만들진 않음
페이징 기법과 다이나믹 로딩은 다른 것이다.

Overlays

• 메모리에 프로세스의 부분 중 실제 필요한 정보만을 올림
• 프로세스의 크기가 메모리보다 클 때 유용
• 운영체제의 지원없이 사용자에 의해 구현
• 작은 공간의 메모리를 사용하던 초창기 시스템에서 수작업으로 프로그래머가 구현
  • "Manual Overlay"
  • 프로그래밍이 매우 복잡

동적로딩과 내용은 비슷하지만 역사적으로 조금 다르다
오버레이는 초창기 컴퓨터 시스템에서 워낙 메모리 크기가 작아서 프로그램 하나를 메모리에 올려놓는 것이 불가능 했다. 프로그래머가 실행시킬땐 프로그램을 쪼개서 수작업으로 실행했는데 => 메뉴얼 오버레이
운영체제의 지원이 없고 프로그래머가 코딩을 통해 올리고 내리는 것을 결정함.
동적 로딩은 라이브러리가 지원되기 때문에 차이가 있다.

Swapping

• Swapping
  • 프로세스를 일시적으로 메모리에서 backing store로 쫓아내는 것
• Backing store(=swap area)
  • 디스크
    • 많은 사용자의 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장 공간
• Swap in / Swap out
  • 일반적으로 중기 스케줄러(swapper)에 의해 swap out 시킬 프로세스 선정
  • priority-based CPU scheduling algorithm
    • 우선순위가 낮은 프로세스를 swapped out 시킴
    • 우선순위가 높은 프로세스를 메모리에 올려 놓음
  • Complie time 혹은 load time binding에서는 원래 메모리 위치로 swap in 해야함
  • Execution time binding에서는 추후 빈 메모리 영역 아무곳에나 올릴 수 있음
  • swap time은 대부분 transfer time(swap되는 양에 비례하는 시간)임

하드디스크에 쫓겨난 걸 저장하는걸 스왑 영역이라고 부른다
메모리에서 통째로 쫓겨나서 백킹 스토어로 가는걸 스왑 아웃, 올라오는걸 스왑 인 이라고 한다
통째로 쫓겨나는 것도 스와핑이라고 한다
일부 페이지가 쫓겨나는 것도 스왑아웃 되었다는 표현을 쓰기도 한다
원칙적인 원래 스왑 아웃은 전체가 쫓겨나는 것이다

Dynamic Linking

• Linking을 실행 시간(execution time)까지 미루는 기법
• Static linking
  • 라이브러리가 프로그램의 실행 파일 코드에 포함됨
  • 실행 파일의 크기가 커짐
  • 동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로 메모리 낭비(eg. printf 함수의 라이브러리 코드)
• Dynamic linking
  • 라이브러리가 실행시 연결(link)됨
  • 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub이라는 작은 코드를 둠
  • 라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고 없으면 디스크에서 읽어온다
  • 운영체제의 도움이 필요

다이나믹 링킹을 해주는 라이브러리를 쉐어드 라이브러리라고 부른다. 리눅스에선 쉐어드 오브젝트, 윈도우즈는 DLL(다이나믹 링킹 라이브러리)

물리적 메모리를 어떻게 관리할 것인가?

Allocation of Physical Memory

• 메모리는 일반적으로 두 영역으로 나뉘어 사용
  • OS 상주 영역
    • interrupt vector와 함께 낮은 주소 영역 사용
  • 사용자 프로세스 영역
    • 높은 주소 영역 사용
• 사용자 프로세스 영역의 할당 방법
  • Contiguous allocation : 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것
    • Fixed partition allocation
    • Variable partition allocation
  • Nonconfiguous allocation : 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있음
    • Paging
    • Sagmentation
    • Paged Segmentation

Contiguous Allocation (연속 메모리 할당)

• 고정 분할(Fixed partition) 방식

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

• 가변 분할(Variable partition) 방식

  • 프로그램의 크기를 고려해서 할당
  • 분할의 크기, 개수가 동적으로 변함
  • 기술적 관리 기법 필요
  • 외부 단편화 발생

• External fragmentation(외부 조각) = 외부 단편화

  • 프로그램 크기보다 분할의 크기가 작은 경우
  • 아무 프로그램에도 배정되지 않은 빈 곳인데도 프로그램이 올라갈 수 없는 작은 분할

• Internal fragmentation(내부 조각) = 내부 단편화

  • 프로그램 크기보다 분할의 크기가 큰 경우
  • 하나의 분할 내부에서 발생하는 사용되지 않는 메모리 조각
  • 특정 프로그램에 배정되었지만 사용되지 않는 공간

• 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들이 생성됨

최초 적합과 최적 적합이 최악 적합보다 속도와 공간 이용률 측면에서 효과적인 것으로 알려졌다 (실험적인 결과)

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

Paging

• Process의 가상 메모리를 동일한 사이즈의 page 단위로 나눔
• 가상 메모리의 내용이 page 단위로 비연속적으로 저장됨
• 일부는 backing storage에, 일부는 physical memory에 저장
  
  
• Basic Method
  • 물리 메모리를 동일한 크기의 frame으로 나눔
  • 논리 메모리를 동일한 크기의 page로 나눔 (frame과 같은 크기)
  • 모든 가용 frame들을 관리
  • page table을 사용하여 논리 주소를 물리 주소로 변환
  • 외부 단편화 문제가 발생하지 않지만 내부 단편화가 발생할 수 있다

배열이 실제로는 테이블이라는 이름으로 많이 사용된다
페이지 내 오프셋부분은 주소 변환에서 영향이 없고 앞에 있는 페이지 번호로 인해 주소 변환이 이루어진다
페이지 테이블은 어디에 들어갈까?
MMU 기법에서는 레지스터 두개로 주소 변환을 했다. 레지스터는 CPU 내에 들어 있는 빠른 장치이다
프로그램을 구성하는 주소 공간을 페이지 단위로 자르는데 보통 페이지 크기가 4KB이다
프로그램의 주소 공간은 굉장히 크다. 그래서 4KB로 자르게 되면 페이지 테이블의 엔트리가 4개라고 치면 실제로는 100만개 정도가 필요하다. 프로그램 하나의 주소 공간이 100만개의 페이지 공간으로 잘린다.
그럼 백만개의 엔트리가 CPU안에 레지스터에 들어갈 수 있을까? 못들어간다.
페이지 테이블은 각 프로세스마다 별도로 존재한다. 페이지 테이블은 메모리에 집어넣는다.

• Page table은 메인 메모리에 있다
• Page-table base register (PTBR)가 page table을 가리킨다 -> 베이스 값
• Page-table length register (PTLR)가 테이블 크기를 보관한다 -> 리미트 값
• 모든 메모리 접근 연산에는 2번의 memory access가 필요하다
• page table 접근 1번, 실제 data/instruction(데이터를 메모리에서 접근하기 위해) 접근 1번
• 속도 향상을 위해 associative register 혹은 translation look-aside buffer(TLB)라 불리는 고속의 lookup hardware cache 사용

기본적인 레지스터 두개가 페이징 기법에선 PTBR과 PTLR로 사용된다.
TLB는 메인 메모리와 CPU 사이에 존재하는 주소 변환을 위한 계층이다. (메인 메모리보다 빠르다)
주소 변환을 위한 캐시 메모리이다. 빈번이 참조되는 일부 엔트리를 캐싱하고 있다.
메인 메모리보다 접근 속도가 빠른 하드웨어로 구성되어 있다
메모리 상에 있는 페이지 테이블을 접근하기 전에 TLB를 먼저 검색해본다
혹시 주소 변환 정보 중에서 TLB에 저장되어있는 정보를 이용해서 주소 변환이 가능한지 확인해본다
페이지 테이블로 가기 전에 TLB에 이미 저장이 되있다면 TLB를 통해 바로 주소 변환이 이뤄진다. 그럼 바로 주소변환을 해서 물리 메모리로 접근하기 때문에 메모리를 1번만 접근하면 된다
없는 경우엔 페이지 테이블을 통해 일반적인 주소변환을 하고 메모리에 접근하기 때문에 2번의 접근이 필요하다
TLB는 전체를 담지 않고 일부만 담고있다. (빈번하게 참조되는)

Associative register

• associative register (TLB) : TLB는 보통 Associative register를 이용해서 구현하고 있다. (병렬 검색 가능)
  가상 메모리 주소를 물리적인 주소로 변환하는 속도를 높이기 위해 사용되는 캐시
  최근에 일어난 가상 메모리 주소와 물리 주소의 변환 테이블 저장
  일종의 주소 변환 캐시

출처 : https://blog.naver.com/kgr2626/222147205118

• Address translation
  • page table 중 일부가 associative register에 보관되어 있다
  • 만약 해당 page #(num)이 associative register에 있는 경우 곧바로 frame #을 얻는다
  • 그렇지 않은 경우 메인 메모리에 있는 페이지 테이블로부터 frame #을 얻는다
  • TLB는 컨텍스트 스위치 때 flush (remove old entries)

메모리에 접근하는 시간

TLB에 접근하는 시간이 e(엡실론)이라고 할 때 접근하는 시간이 메인 메모리에 접근하는 시간인 1보다 작다
TLB로부터 주소 변환이 되는 비율을 알파라고 했을 때 실제로 메모리에 접근하는 시간을 계산하면

2보다는 훨씬 작은 값이 된다 (어떻게 계산하는지 잘 모르겠다..)

Two-Level Page Table (2단계 페이지 테이블)

page table을 위한 공간을 줄이기 위해 사용. 속도는 줄어들지 않는다
현대의 컴퓨터는 address space가 매우 큰 프로그램을 지원한다

• 32 bit address 사용시 : 2^32(4G)의 주소 공간
  • page size가 4K시 1M개의 page table entry가 필요하다
  • 각 page entry가 4B시 프로세스 당 4M의 page table이 필요하다
  • 그러나 대부분의 프로그램은 4G의 주소 공간 중 지극히 일부분만 사용하므로 page table 공간이 심하게 낭비된다

-> page table 자체를 page로 구성
-> 사용되지 않는 주소 공간에 대한 outer page table의 엔트리 값은 NULL(대응하는 inner page table이 없음)

2단계 페이징 테이블 기법에서는 바깥 페이지 테이블은 전체 논리적 메모리 크기만큼 만들어지지만, 실제로 사용하지 않는 주소에 대해서는 안쪽 페이지 테이블을 만들어두지 않고 null로 남겨둔다.
그럼 이걸 왜 사용하느냐? 페이지 테이블의 공간을 줄일 수 있기 때문인데, 어떻게 줄이느냐?
전체 주소 공간 중 상당 부분이 실제로 사용이 안되는 공간이기 때문에(그래서 안쪽 페이지 테이블이 만들어지지 않기 때문에) 그런것이다

Multilevel Paging and Performance (다단계 페이지 테이블)

• Address space가 더 커지면 다단계 페이지 테이블이 필요하다
• 각 단계의 페이지 테이블이 메모리에 존재하므로 logical address의 physical address 변환에 더 많은 메모리 접근이 필요하다
• TLB를 통해 메모리 접근 시간을 줄일 수 있다
• 4단계 페이지 테이블을 사용하는 경우
  • 메모리 접근 시간이 100ns, TLB 접근 시간이 20ns이고
  • TLB hiy ratio가 98%인 경우 effective memory access time = 0.98 120 + 0.02 520 = 128 ns
    결과적으로 주소 변환을 위해 28ns만 소요된다

페이지 테이블에 주소변환정보만 들어있는 것이 아니고 부가적인 비트가 엔트리마다 같이 저장된다

Memory Protection

Page table의 각 엔트리마다 아래의 bit를 둔다

• Protection bit
  • 페이지에 대한 접근 권한(read/write/read-only)
  • 연산에 대한 권한을 표시하기 위한 비트
• valid-invalid bit
  valid라는 것은 실제로 물리적인 메모리에 올라와 있다는 것이고 invalid는 이 페이지가 프로그램에서 사용되지 않거나 페이지가 메모리에 당장 올라가지 않을 수도 있다.
  - valid : 해당 주소의 프레임에 그 프로세스를 구성하는 유효한 내용이 있음을 뜻함 (접근 허용)
  - invalid : 해당 주소의 프레임에 유효한 내용이 없을 뜻함 (접근 불허)
  - 프로세스가 그 주소 부분을 사용하지 않는 경우
  - 해당 페이지가 메모리에 올라와 있지 않고 swap 영역에 있는 경우

Inverted Page Table

페이지 테이블의 문제는 굉장히 많은 용량을 차지하고 있다는 것이다. 주소 공간이 허용하는 한도 만큼 페이지 테이블이 만들어져야 하고 또 프로세스마다 각각 주소 변환을 해야하기 때문에 각 프로세스 별로 페이지 테이블이 만들어져야하기 때문에 굉장히 공간 오버헤드가 컸다. 그걸 막아보기위해 나온 것이 Inverted Page Table이다

• Page table이 매우 큰 이유
  • 모든 프로세스 별로 그 논리적 주소에 대응하는 모든 페이지에 대해 페이지 테이블 엔트리가 존재
  • 대응하는 페이지가 메모리에 있든 아니든 간에 페이지 테이블에는 엔트리로 존대
• Inverted page table
  - 페이지 프레임 하나 당 페이지 테이블에 하나의 엔트리를 둔 것 (system-wide)
  - 각 페이지 테이블 엔트리는 각각의 물리적 메모리 페이지 프레임이 담고 있는 내용 표시 (프로세스 id, 프로세스의 논리 주소)
  - 단점 : 테이블 전체를 탐색해야 함
  - 조치 : associative register 사용 (비쌈)
  

원래의 페이지 테이블을 통한 주소 변환을 완전히 역발상으로 뒤집어 놓은 것이다.
시스템 안에 페이지 테이블이 각 프로세스마다 존재하는 것이 아닌, 단 하나 존재한다.
페이지 테이블의 엔트리가 물리적 메모리의 페이지 프레임 개수만큼 존재한다.
우리가 주소 변환을 하려면 논리 주소에서 페이지 번호를 보고 페이지 테이블에서 번호만큼 떨어진 엔트리에 가서 주소 변환을 하는 방법을 사용했는데, Inverted Page Table은 그것이 불가능하다. 이유는 정방향으로 주소 변환을 하는 것이 아닌 페이지 프레임의 논리적인 번호가 나오게 되어있다. 주소 변환은 논리 주소를 물리 주소로 바꾸는 것이지 이것은 물리 주소를 보고 논리 주소로 바꿀 수 있는 테이블이다. 우리 목적에 맞지 않는 테이블인데, 논리 주소에 해당하는 페이지 번호 p가 물리적 메모리의 어디에 올라가 있는지를 찾으려면 페이지 테이블 엔트리를 다 찾아봐야한다.

Shared Page (공유 페이지)

페이징 기법의 장점 중 하나는 코드를 공유할 수 있는 가능성이다.

공유페이지를 하기 위해선 재진입가능 코드여야 하며, 읽기 전용 특성을 코드에게만 의존하는 것이 아니라 운영체제가 이 속성을 강제해야한다

• Shared code
  • Re-entrant Code (=Pure Code) 재진입가능 코드, 실행 중에 변하지 않는 코드
    • 따라서 둘 이상의 프로세스가 동시에 같은 코드를 실행할 수 있다. 즉, 각 프로세스는 동일한 코드를 서로 다른 데이터로 실행한다
  • read-only로 하여 프로세스 간에 하나의 코드만 메모리에 올림 (eg, text editors, compilers, windows systems)
  • Shared code는 모드 프로세스의 논리 주소 공간에서 동일한 위치에 있어야 한다
• Private code and data
  • 각 프로세스들은 독자적으로 메모리에 올림
  • Private data는 논리 주소 공간의 아무 곳에 와도 무방

Segmentation

프로그램은 의미 단위인 여러개의 세그먼트로 구성되어 있다.

• 작게는 프로그램을 구성하는 함수 하나하나를 세그먼트로 정의
• 크게는 프로그램 전체를 하나의 세그먼트로 정의 가능
• 일반적으로는 code, data, stack 부분이 하나씩의 세그먼트로 정의됨
• 논리주소는 segment-number와 offset으로 구성되어 있다

Segment table

• base - starting physical address of the segment. 물리 주소에서의 세그먼트의 시작 위치
• limit - length of the segment. 물리주소에서의 세그먼트의 길이

Segment-table base register (STBR)

물리적 메모리에서의 세그먼트 테이블의 위치

Segment-table length register (STLR)

프로그램이 사용하는 세그먼트의 수. 논리주소의 세그먼트 번호가 STLR보다 작아야한다. 크다면 트랩에 걸린다