Address translation & Segmentation

이번 포스트는 OS의 Address translation 과 Segmentation 에 대해 다룬다.

Address translation

Memory Virtualizing with Efficiency and Control

• 메모리 가상화 (memory virtualization)도 CPU 가상화(LDE)랑 똑같은 목표를 가진다.
  • 여러 프로세스가 각자 메모리를 전부 쓰는 것처럼 보이게 만들기
  • 동시에 효율(빨라야 한다.) + 제어(안전해야한다.) 를 둘 다 만족해야 한다.
• CPU 쪽에서 LDE (Limited Direct Execution)가 했던 것:
  • 효율 : 유저 프로그램을 진짜 CPU에서 직접 돌림 (가능한 한 빠르게)
  • 제어 : 시스템 콜 / 트랩 / 타이머 인터럽트로 OS가 항상 최종 제어권을 가진다.
• 메모리 가상화도 마찬가지다.
  • 가능한 한 직접 메모리에 접근하는 것처럼 빠르게 만들어야 한다.
  • 동시에, 다른 프로세스 메모리에 함부로 못 쓰게 OS가 통제해야 한다.

이걸 위해 하드웨어 지원이 꼭 필요하다.

(예시)

1. 레지스터 : 주소 변환에 필요한 기준 값을 저장
2. TLB (Translation Look-Aside Buffer) : 가상 -> 물리 주소 변화 결과를 캐시
3. Page-table : 전체 주소 변환 규칙을 저장해둔 테이블

Address Translation

개념 : 가상 주소 (Virtual Address) -> 물리 주소 (Physical Address) 변환 과정

• 프로세스 입장 : 0x400000 같은 가상 주소만 본다.
• 실제 RAM 안에서 데이터가 있는 위치는 물리 주소
• 하드웨어 (MMU)가 이 둘을 실시간으로 매 접근마다 변환해 준다.

이런 변환이 필요한 이유?

1. 각 프로세스마다 독립적인 주소 공간 (illusion)을 주기 위해
   • 서로 같은 가상주소를 써도 다른 물리 주소로 매핑된다.
2. 보호 (Protection)
   • 한 프로세스의 가상 주소가 다른 프로세스 물리 메모리로는 매핑이 안 되게 설정이 가능하다.
3. 유연한 배치
   • 프로그램을 물리 메모리 여기저기 흩뿌려두고, 가상 주소로는 연속인 것처럼 보이게 할 수 있다.

OS 의 역할

• 하드웨어 혼자서 매핑 규칙을 만들 수가 없다.
  • 프로세스 생성 시, 페이지 테이블 / 세그먼트 테이블 같은 변환 규칙을 세팅해야 한다.
  • 이 정보를 하드웨어 (MMU)에게 알려준다.
  • 페이지 교체, 프로세스 종료 등 상황 변화에 따라 매핑을 갱신한다.

실제 동작 과정

void func() {
    int x = 3000;
    ...
    x = x + 3;
}

x = x + 3 : CPU는 다음 두 단계로 나누어 처리

• 메모리에 있는 변수 x 값을 읽어서 레리스터로 가져오고 (load)
• 3을 더한 뒤에, 다시 메모리에 저장한다. (store)

128: movl 0x0(%ebx), %eax   ; 메모리(0+ebx) → eax
132: addl $0x03, %eax       ; eax = eax + 3
135: movl %eax, 0x0(%ebx)   ; eax → 메모리(0+ebx)

변수 x 의 메모리 주소가 EBX 레지스터에 이미 저장돼 있다고 가정

1. Load : movl 0(%ebx), %eax
   • EBX가 가리키는 주소의 값을 EAX로 가져옴
2. Add : addl $3, %eax
   • EAX = EAX + 3
3. Store : movl %eax, 0(%ebx)
   • EAX 값을 다시 EBX가 가리키는 메모리 주소에 저장

Example : Address Translation

실제 6단계의 실행 순서

1. Instruction Fetch (주소 128)
   • CPU는 PC 에서 128 이라는 가상주소를 읽고
   • 해당 위치의 명령어 movl 0(%ebx), %eax를 가져온다. (fetch)
2. Execute
   • EBX가 가리키는 주소 (=15KB)에서 값을 읽어 EAX로 옮긴다.
   • 이 과정에서 Address Translation이 필요하다.
   • Virtual Address -> Physical Address
3. Fetch Instruction (주소 132)
   • addl 명령어를 가져온다.
4. Execute
   • 3을 더하는 명령어 실행
   • 이때는 메모리의 접근이 없다.
5. Fetch Instruction (주소 135)
   • movl %eax, 0(%ebx) 명령어를 가져온다.
6. Execute
   • EAX의 값을 EBX가 가리키는 메모리(15KB)에 저장한다.
   • 이때도 VA -> PA 의 변환을 거친다.

Dynamic Relocation

프로세스의 주소 공간 (Address Space)은 항상 0KB부터 시작한다고 가정한다. 하지만 실제 물리 메모리에서는 절대 0KB에 둘 수가 없다.

• 0KB ~ 일정 영역 = OS가 차지하고 있기 때문
• 여러 프로세스를 올리려면 메모리 다양한 위치에 올려야 한다.

따라서 OS는 프로세스를 물리 메모리의 아무 곳(어디든)에서 실행을 시켜야 한다. => Dynamic Relocation (동적 재배치)

Base & Bounds (Limit) Register

Dynamic Relocation을 하드웨어적으로 구현하는 방식

Base Register (베이스 레지스터)

• 가상 주소공간의 0KB가 물리 주소 어디에 위치하는가?를 저장한다.
• 프로세스의 시작 위치를 저장하는 레지스터

가상 주소 + base = Physcial Address

Bounds Register (Limit Register)

• 프로세으의 주소 공간의 길이

• 이 주소 이상 접근을 하려고 하면 메모리가 침범되기 때문에 OS가 차단을 한다.

  • 이 과정은 모든 메모리 참조마다 하드웨어가 반복해준다.
  \[0 ≤ Virtual Address < Bounds\]

• 모든 가상 주소는 0 이상, Bound (프로세스 크기) 미만이어야 한다.

-> 앞선 예시 다시보기

128 : movl 0x0(%ebx), %eax

128(가상 주소)에 위치한 명령어를 fetch하고 수행해야 하는데, 프로세스는 물리 주소 32KB에 위치해 있을때,

• Fetch 주소 변환

Virtual Instruction Address = 128

Base = 32KB (32768)

Physical = Virtual + Base = 32896

CPU는 물리 주소 32896에서 명령을 가져온다.

• Load 주소 변환

load from address 15KB

15KB = 가상주소

Physical = 15KB + 32KB = 47 KB

Bounds Register의 두 가지 해석

1. Bounds = Address Space Size

• 주소 공간 크기를 그대로 저장
  • 가상 주소가 0~(bounds)~1 내에 있는지 체크
  • base는 따로 존재

\[Virtual Address < Bounds\]

2. Bounds = Physical Address of End

• 주소 공간의 물리 끝 주소를 저장

\[(Virtual + Base) < Bounds\]

OS Issues

운영체제는 Base&Bounds 방식이 자동으로 굴러가게 하지 않는다.

OS가 반드시 개입해야 할 4개의 시점이 존재한다.

1. When a Process Starts Running

• 프로세스를 메모리에 올릴 때 필요한 크기 만큼의 연속 공간을 찾아야 한다.

Free list

• 물리 메모리에서 사용 중이 아닌 연속 구간들의 목록
• 각 노드에는 ‘얼마 만큼 비어 있는지’를 표시됨.

동작 과정

1. OS는 free list를 확인한다.
2. 새 프로세스가 예를 들어 16KB 가 필요하면
3. free list의 노드를 확인하고 알맞은 공간을 선택한다.
4. 선택한 공간에 프로세스를 적재하고 base register에 그 물리주소를 넣는다.

2. When a Process is Terminated

• 프로세스가 사라지면 사용하던 메모리 공간을 free list에 다시 추가하는 과정

동작 과정

1. Process A가 종료된다.
2. 그 프로세스가 차지하던 물리 메모리 공간을 OS가 확인한다.
3. Free list에 다시 32KB free (예시) 노드를 추가한다.
4. 그리고 Free list 정렬 / 병합 작업도 필요할 수도 있음.

정렬 병합 작업 : memory Fragmentation

3. When Context Switch Occurs

• Context Switch -> 단순히 레지스터 / PC만 바꾸는 것이 아니라 메모리 보호 정보 (= base, bounds)도 함께 바꿔야 한다.

Context Switch 과정

1. CPU가 Process A의 base/bounds 값을 A의 PCB에 저장한다.
2. CPU가 Process B를 실행할 때
   • PCB에서 B의 base 값을 읽어와 Base Register에 넣는다.
   • PCB에서 B의 bounds 값을 읽어와 Bounds Register에 넣는다.
3. 이제 CPU가 주소 변환을 할 때
   • Virtual Address + Base(Register) = Physical Address 를 올바르게 계산이 가능하다.

---

Segmentation

위에서 설명한 Base & Bound 방식에는 비효율적인 요소가 존재한다.

문제상황 1 : Address Space 전체를 통째로 올려야 한다.

• Base & Bound (= Dynamic Allocation)은 하나의 프로세스 주소 공간 전체를 한 덩어리로 물리 메모리에 올려야 한다.
  • Heap은 위쪽 대부분이 Free 한 공간이다.
  • Stack 아래에도 많은 free 공간이 존재한다.
    • 실제로 사용을 하지 않아도 그 공간까지를 모두 차지하는 것이기에 비효율적이다.

비유 : 실제로는 4칸짜리 책상을 사용하는것이지만, 16칸짜리를 무조건 통째로 예약해둬야 하는 상황

문제 상황 2 : 물리 메모리에 충분한 연속된 공간이 없으면 실행이 불가능하다.

• 공간이 남아있어도 연속 공간이 부족하면 실행이 안된다.

문제 상황 3 : 외부 단편화 (External Fragmentation) 발생

• 큰 Contiguous block을 요구하기에 중간중간 작은 조각만 남으면 공간이 있어도 못 넣는다.

Segmentation

개념 : 프로세스의 Address Space를 여러 조각 (Segment)로 나누어 관리하는 방식

예시 : 논리적으로 구분되는 영역 3가지

• Code Segment
• Heap Segment
• Stack Segment

이 3가지는 사실 서로 연속될 필요가 없다.

Segmentation의 핵심 특징

1. Address Space를 여러 Segment로 나눈다.

• 기존처럼 프로세스 전체를 한 덩어리로 보는게 아니라, 각 영역을 별도의 segment로 관리한다.

2. 각 Segment를 물리 메모리의 “다른 위치”에 배치할 수 있다.

• 물리 공간이 연속이지 않아도 된다.
• 예시)
  • Code : 100KB / Heap : 300 KB / Stack : 250 KB

3. Base&Bound는 각 Segment당 하나씩 존재한다.

• base register : 해당 segment 가 물리 메모리 어디에 있는가
• bounds register : segment의 길이를 제한 한다.

Address Translation on Segmentation \(physcial address = base + offset\) 예를 들어 Virtual Address = 100, size = 2KB 인 code의 segmentation을 구해보면 \(Physical address = 100 + (32 * 1024) = 32868\)

그냥 Virtual Address + base가 정확한 physical Address를 구하는 것이 아니다.

OFFSET of Virtual Address + Base가 올바른 계산이다.

Segmentation Fault

• Segmentation 에서는 각 세그먼트마다 크기 (=bounds)가 정해져있다.
  • Heap의 크기가 2KB 라면, Heap 세그먼트 내부에서 offset이 2KB까지만 유효하다.

만약 세그먼트의 끝 부분보다 더 큰 주소에 접근한다면?

• 세그먼트 밖의 주소는 절대 접근하면 안된다.
• 하드웨어가 자동으로 감지하고 OS가 프로세스를 종료한다.

Referring to Segment

세그먼트의 구분 방식

• Segmentation은 보통 virtual address 의 상위 몇 비트를 사용하여 세그먼트를 구분한다.

예 : virtual Address = 14bit

-> 상위 2 bit : 세그먼트 ID / 나머지 12bit : Offset

• 상위 2 bit

Segment	Bits
Code	00
Heap	01
-	10
Stack	11

• 주소 변환 알고리즘

Segment = (VirtualAddress & SEG_MASK) >> SEG_SHIFT
Offset  = VirtualAddress & OFFSET_MASK

if (Offset >= Bounds[Segment])
    RaiseException(PROTECTION_FAULT)
else
    PhysAddr = Base[Segment] + Offset

흐름 요약

1. Virtual Address에서 세그먼트 번호 추출
2. VA에서 offset 추출
3. offset이 bounds 이하인지 확인
4. 실제 물리주소 = base + offset
5. AccessMemory (물리주소)

Stack Segment

• 위의 예시와 다르게 Stack은 메모리가 아래 방향(backward)로 자라는 구조이다.
  • 주소가 감소하는 방향으로 push가 일어난다.
• 따라서 보통의 segment는 증가 방향이지만, stack은 반대로 감소 방향을 가짐

이걸 처리하기 위해 하드웨어가 방향까지 알아야 한다.

• 수식

\[negative offset = offset - maximum_segment_size\] \[physical = negative offset + base\]

Sharing

• Segmentation의 장점 중 한개
• 다른 프로세스끼리 동일한 Segment를 공유할 수 있다.
  • 한 프로그램을 여러 번 실행하면 코드 부분은 거의 항상 동일하기에 공유가 가능하다.
• 예시 ) 프로세스 A, B가 같은 실행 파일을 실행할때
  • Code Segment를 하나의 메모리에 두고
  • 둘 다 그 Segment를 base-register로 가리키게 하면 된다.

Protection Bits (보호 비트)

• Segment 마다 read, write, execute 권한을 붙여서 잘못 된 접근을 막는다.
  • Code Segment는 실행 가능하지만 수정하면 안됨 : Read-Execute
  • Heap/Stack은 데이터를 저장해야함 : Read-Write

만약 Segment는Write 가 금지인데 write를 수행하면 segmentation fault 와 같은 보호를 가능하게 해준다.

Fine-Grained vs Coarse-Grained

Coarse-Grained Segmentation

• 세그먼트의 개수가 적다
  • 예 ) code, heap, stack 정도만 있다.
• 관리가 쉽기는 하지만 유연성이 부족하다.

Fine-Grained Segmentation

• 세그먼트의 개수를 더 많이 나눌 수 있다.
  • 예) 함수별 segment, 라이브러리별 segment
• 유연성이 증가한다.
• 세그먼트 개수를 더 많이 나눌 수 있다.
• 많은 segment를 관리하기 위해 Segment Table이 필요하다.

Fragmentation

External Fragmentation : 조각난 free space 때문에 segment를 올릴 수 없는 상황

• 빈 공간의 총합이 여유가 있지만, 연속된 공간이 없는 경우 => allocation 실패

Compaction : 메모리 내 segment 들을 재배치 (압축)

• free space를 한 덩어리로 만들기 위한 작업
• cost가 매우 비싸다.
• 절차

1. 프로세스의 실행을 중단한다.
2. 메모리 블록들을 복사하여 연속되게 재배치한다.
3. segment base register의 값을 재설정한다.

실제 시스템에서 compaction은 거의 안쓰거나 제한적으로만 사용된다.