세그멘테이션

프로세스를 물리 메모리에 재배치하는 방법으로는 베이스/바운드 레지스터를 사용하는 방법이 있다.
이 방법에는 단점이 있는데, 스택과 힙 사이에 사용되지 않는 공간이 크다는 것이다.
즉, 메모리 낭비가 심하고, 유연성이 없다는 단점이 존재한다.

핵심질문: 대용량 주소 공간을 어떻게 지원하는가
스택과 힙 사이에 잠재적으로 큰 빈 영역이 존재하는 주소공간을 어떻게 지원해야 할까?

1. 세그멘테이션: 베이스/바운드의 일반화

세그멘테이션(segmentation): MMU 안의 세그먼트마다 베이스와 바운드 쌍이 존재하도록 논리 주소공간을 설계한 것

• 운영체제는 각 세그먼트를 물리 메모리의 각기 다른 위치에 배치 가능
• 사용되지 않는 가상주소 공간이 물리 메모리를 차지하는 것을 방지
• 기존의 베이스/바운드 방식
  
• 세그멘테이션 방식
  
  • 스택 세그먼트의 베이스 값은 28KB, 크기는 2KB (바운드)
  • 코드 세그먼트의 베이스 값은 32KB, 크기는 2KB (바운드)
  • 힙 세그먼트의 베이스 값은 34KB, 크기는 2KB (바운드)
  • 예시
    (첫번째 그림을 두번째 그림으로 바꾸기)
    • 가상주소 100번지 -> 코드 세그먼트
      물리주소 = 베이스 + 오프셋 = 32KB + 100 = 32868
      참고) 오프셋: 변위차, 상대주소
    • 가상주소 4200번지 -> 힙 세그먼트
      물리주소 = 베이스 + 오프셋 = 34KB + (4200 - 4KB)
      = 34KB + 104 = 34920
      (힙이 가상주소 4KB에서 시작하므로 4KB를 빼줌)
    • 가상주소 7KB -> 힙의 마지막을 벗어난 경우 (크기 2KB임)
      물리주소 = 베이스 + 오프셋 = 34KB + (7KB - 4KB) = 37KB
      -> 세그먼트 폴트(segment fault) 발생

2. 세그멘트 종류의 파악

1) 가상 주소의 최상위 몇 비트로 세그먼트 나누기

• 가상 주소의 최상위 몇 비트를 기준으로 주소 공간을 여러 세그먼트로 나누는 것
• 예시로 최상위 2 비트를 세그먼트로, 나머지를 주소 공간의 상대 위치인 오프셋으로 사용
• 이 경우 총 4개의 세그먼트로 나눌 수 있음 (세그먼트 00, 01, 10, 11)
  • 근데 사용할 영역은 3개(코드, 힙, 스택) 이므로 전체 주소 공간의 1/4을 사용할 수 없다는 단점
  • 일부 시스템은 코드와 힙을 하나의 세그먼트에 저장하고, 1비트만 사용

2) 묵시적(implicit) 접근방식

• 주소가 어떻게 형성되었나를 관찰하여 세그먼트 결정
• 특정 주소의 세그먼트를 하드웨어적으로 파악
• 예시
  • 주소가 프로그램 카운터에서 형성되었다면 (명령어 반입) 주소코드는 코드 세그먼트에 있을 것
  • 주소가 스택 또는 베이스 포인터에 기반을 둔다면, 주소는 스택 세그먼트에 있을 것
  • 다른 주소는 모두 힙에 있을 것

3. 스택

스택은 다른 세그먼트들과 반대 방향으로 확장된다.

• 물리 메모리 28KB에서 시작해서 26KB까지 차지
• 가상 주소 16KB에서 14KB에 해당
• 다른 방식의 변환 필요

세그먼트 레지스터 추가

• 하드웨어가 세그먼트가 어느 방향으로 확장하는지 알게끔 세그먼트 레지스터 추가
• 하드웨어는 베이스, 바운드, 세그먼트 레지스터 세 개 필요
  
• 반대 방향으로 확장하므로 음수 오프셋이 나와야 함
• 예) 가상주소 15KB 바꾸기
  • 15KB는 물리주소 27KB에 매핑되어야 함
  • 가상주소 15KB의 이진수: 11 1100 0000 0000
  • 상위 2비트(11)을 사용하여 세그먼트 지정
  • 그러면 1100 0000 0000 -> 3KB의 오프셋이 남음
  • 올바른 음수 오프셋을 얻기 위해 세그먼트 최대 크기인 4KB를 빼면 -1KB를 얻을 수 있다.
  • 물리주소 = 베이스 + 오프셋 28KB + (-1KB) = 27KB

4. 공유 지원

메모리 절약을 위해 주소공간들 간에 특정 메모리 세그먼트를 공유하는 것이 유용하다.
특히 코드 공유가 유용하고, 현재 시스템에서도 광범위하게 사용중이다.

공유 지원

• 하드웨어에 protection bit 추가 (베이스, 바운드, 세그먼트, 보호)
  
• 세그먼트를 읽기/쓰기/실행시킬 수 있는지 나타냄
  • 코드 세그먼트 읽기전용으로 설정
    -> 주소 공간의 독립성 + 여러 프로세스가 주소 공간의 일부 공유
  • 각 프로세스는 여전히 자신의 전용 메모리를 사용하고 있다고 착각
  • 운영체제는 변경이 불가능하도록 설정된 메모리 영역을 비밀리에 공유시킴
• 코드 세그먼트는 읽기 및 실행으로 설정됨
  -> 같은 물리 세그먼트가 여러 가상 주소 공간에 매핑될 수 있음
• 이제는 가상 주소가 범위 내에 있는지 확인하는 것 이외에 특정 액세스가 허용되는지도 확인해야 함
  • 읽기 전용에 쓰기를 시도하면 에러
  • 실행 불가한데 실행하려고 하면 에러

5. 소단위 대 대단위 세그멘테이션

대단위 세그멘테이션(coarse-grained)

• 소수의 세그먼트만을 지원하는 시스템
  • 코드, 스택, 힙만을 지원
• 주소공간을 비교적 큰 단위의 공간으로 분할
• 세그먼트의 수가 줄어 관리가 편하며 하드웨어가 간단해진다

소단위 세그멘테이션(fine-grained)

• 주소공간을 작은 크기의 공간으로 분할
• 많은 수의 세그먼트를 지원해야 하므로 세그먼트 테이블 필요
• 메모리를 효율적으로 활용 가능

6. 운영체제의 지원

세그멘테이션은 새로운 문제를 많이 제기한다.

문맥 교환 시 운영체제는 어떤 일을?

• 운영체제는 세그먼트 레지스터의 저장과 복원을 해야한다.
• 각 프로세스는 자신의 가상 주소 공간을 가짐
  -> 운영체제는 프로세스가 다시 실행하기 전에 레지스터들을 올바르게 설정

미사용중인 물리 메모리 공간의 관리는?

• 프로세스가 많은 세그먼트를 가질 수 있고, 각 세그먼트는 크기가 다를 수 있다
• 외부 단편화(external fragmentation)
  • 남아있는 총 메모리 공간이 요청한 메모리 공간보다 크지만, 남아있는 공간이 연속적(contiguous)이지 않아 발생하는 현상
  • 물리 메모리가 빠르게 작은 크기의 빈 공간들로 채워지면
    1. 빈공간을 새 세그먼트에 할당하기도 힘듦
    2. 기존 세그먼트를 확장하는 데에도 도움이 되지 않음
       
    • 위의 경우, 24KB의 빈 공간이 있지만, 연속적이지 않아 운영체제가 20KB의 요청을 충족시킬 수 없음
• 물리 메모리 압축
  • 기존의 세그먼트를 정리하여 하나의 연속된 공간에 복사하고, 새로운 물리 메모리 위치를 가리키게 함
    
    • 근데 압축은 메모리 부하가 크고, CPU 시간도 많이 사용 (고비용)
• 빈 공간 관리 알고리즘 사용
  • 최적 적합(best-fit)
  • 최악 적합(worst-fit)
  • 최초 적합(first-fit)
  • 버디 알고리즘(buddy algorithm)
  • 등등

    참고) 외부 단편화를 최소화하는 알고리즘이 많다. 이는 곧 "최선"의 해법이 존재하지 않는 뜻이다.

7. 요약

세그멘테이션의 장점

• 효과적인 메모리 가상화
• 동적 재배치 가능
• Sparse address space (드문드문 사용되는 주소공간) 어느정도 개선
• 세그멘테이션에 필요한 산술연산은 쉽고, 하드웨어 구현에 적합하여 속도가 빠름
• 변환 오버헤드가 최소
• 코드가 별도 세그먼트에 존재한다면, 여러 프로그램에서 공유 가능

세그멘테이션의 단점

• 세그먼트의 크기가 일정하지 않아 외부 단편화 발생
• Sparse address space (드문드문 사용되는 주소공간)를 지원할 만큼 충분히 유연하지는 못함
  • 크기가 크지만, 드문드문 사용되는 힙이 하나의 논리적인 세그먼트에 배정된 경우
    -> 이 힙에 접근하려면, 힙 전체가 여전히 물리 메모리에 존재해야함
  • 즉 주소 공간이 사용되는 모델과, 이를 지원하기 위한 세그멘테이션 설계 방법이 정확히 일치해야함