주소 바인딩

• 논리적 주소 혹은 가상 주소 : 프로그램이 실행을 위해 메모리에 적재되면 그 프로세스를 위해 생성되는 독자적인 주소 공간
• 물리적 주소 : 물리적 메모리에 실제로 올라가는 위치, 낮은 주소 영역에는 운영체제가, 높은 주소 영역에는 사용자 프로세스들이 올라감
• 주소 바인딩 : 프로세스의 논리적 주소를 물리적 메모리 주소로 연결시켜주는 작업
  • 프로그램이 적재되는 물리적 메모리의 주소가 결정되는 시기에 따라 3가지로 분류
  1. 컴파일 타임 바인딩 (compile time binding)
     • 프로그램을 컴파일할 때 물리적 메모리 주소가 결정되는 주소 바인딩 방식
     • 컴파일을 하는 시점에 해당 프로그램이 물리적 메모리의 몇 번지에 위치할 것인지를 결정
     • 프로그램이 절대주소로 적재된다는 뜻에서 절대코드를 생성하는 바인딩 방식이라고도 부름
     • ❌ 물리적 주소를 변경하고 싶다면 컴파일을 다시 해야 함 ⇒ 비현실적, 잘 사용 x
  2. 로드 타임 바인딩 (load time binding)
     • 프로그램의 실행이 시작될 때 물리적 메모리 주소가 결정되는 주소 바인딩 방식
     • 로더(사용자 프로그램을 메모리에 적재시키는 프로그램)의 책임하에 물리적 메모리 주소가 부여되며 프로그램이 종료될 때까지 물리적 메로이상의 위치가 고정됨
     • 컴파일러가 재배치 가능 코드를 생성한 경우, 가능한 방식
  3. 실행시간 바인딩 (execution time binding 또는 run time binding)
     • 프로그램이 실행을 시작한 후에도 그 프로그램이 위치한 물리적 메모리상의 주소가 변경될 수 있는 바인딩 방식
     • CPU가 주소를 참조할 때마다 해당 데이터가 물리적 메모리의 어느 위치에 존재하는지, 주소 매핑 테이블(address mapping table)을 이용해 바인딩을 점검해야 함
     • 다른 방식들과 달리 기준 레지스터와 한계 레지스터를 포함해 MMU(Memory Management Unit, 메모리 관리 유닛 : 논리적 주소를 메모리 주소로 매핑해주는 하드웨어 장치) 필요함
• MMU 기법 : 가장 기본적인 방식으로 주소 변환을 수행하는 기법
  • 특정 프로세스의 주소값에 기준 레지스터의 값을 더해 물리적 주소값을 얻어냄
  • 프로그램의 주소공간이 물리적 메모리의 한 장소에 연속적으로 적재되는 것을 가정
  • 한계 레지스터 : 현재 CPU에서 수행 중인 프로세스의 논리적 주소의 최댓값, 즉 그 프로세스의 크기, 프로세스가 자신의 주소 공간을 넘어서는 메모리 참조를 하려고 하는지 체크하는 용도로 사용
  1. 프로세스의 논리적 주소값이 한계 레지스터보다 작은지 확인
  2. 작다면, 논리적 주소값에 기준 레지스터 값을 더해 물리적 주소를 구한 다음 해당 물리적 메모리 위치에 접근하도록 허락
  3. 크다면, 다른 프로세스의 주소 영역에 접근하려는 시도이므로 트랩을 발생시켜 해당 프로세스 강제종료

메모리 관리와 관련된 용어

동적로딩

• 여러 프로그램이 동시에 메모리에 올라가서 수행되는 다중 프로그래밍 환경에서 메모리 사용의 효율성을 높이기 위해 사용하는 기법
• 프로세스 실행 시 프로세스의 주소 공간 전체가 메모리에 적재되는 것이 아니라, 실행에 필요한 부분이 실제로 불릴 때마다 메모리에 적재하는 방식
• ✅ 메모리 이용의 효율성 향상

동적연결

• 연결 : 프로그래머가 작성한 소스 코드를 컴파일하여 생성된 목적 파일과 이미 컴파일된 라이브러리 파일들을 묶어 하나의 실행파일을 생성하는 과정
• 정적연결 : 프로그래머가 작성한 코드와 라이브러리 코드가 모두 합쳐져서 실행파일 생성 ⇒ 실행파일의 크기가 상대적으로 크고, 동일한 라이브러리를 각 프로세스가 개별적으로 메모리에 적재해야 하므로 물리적 메모리가 낭비됨
• 동적연결 : 컴파일을 통해 생성된 목적 파일과 라이브러리 파일 사이의 연결을 프로그램의 실행 시점까지 지연시키는 방법
  • 정적연결과 달리 라이브러리가 실행 시점에 연결되기 때문에 실행 파일에 라이브러리 코드가 포함되지 않으며, 프로그램이 실행되면서 라이브러리 함수를 호출할 때가 되어서야 라이브러리에 대한 연결이 이루어짐
  • 실행파일의 라이브러리 호출 부분에 해당 라이브러리 위치를 찾기 위한 스텁(stub)이라는 작은 코드를 두고 라이브러리 호출 시 스텁을 통해 해당 라이브러리가 메모리에 이미 존재하는지 확인 ⇒ 있으면 직접 참조, 없으면 디스크에서 찾아 적재한 후 수행
  • ✅ 다수의 프로그램이 공통으로 사용하는 라이브러리를 메모리에 한 번만 적재하므로 메모리 사용의 효율성 향상

중첩 (overlays)

• 프로세스의 주소 공간을 분할해 실제 필요한 부분만을 메모리에 적재하는 기법
• 중첩 vs 동적로딩
  • 중첩 : 초창기 컴퓨터 시스템에서 물리적 메모리의 크기 제약으로 인해 하나의 프로세스조차 메모리에 한꺼번에 올릴 수 없을 때, 프로세스의 주소 공간을 분할해서 당장 필요한 부분만 울리기 위해 사용했음 ⇒단일 프로세스만 메모리에 올려놓는 환경에서 메모리 용량보다 큰 프로세스를 실행하기 위해
  • 동적로딩 : 다중 프로그래밍 환경에서 메모리 이용률 향상을 위해 사용 ⇒ 메모리에 더 많은 프로세스를 동시에 올려놓고 실행하기 위해

스와핑 (swapping)

• 메모리에 올라온 프로세스의 주소 공간 전체를 디스크의 스왑 영역에 일시적으로 내려놓는 것
• 다중 프로그래밍의 정도(메모리에 존재하는 프로세스의 수)를 조절하기 위해 사용
• 스왑 영역, 백킹스토어
  • 디스크 내에 파일 시스템과는 별도로 존재하는 일정 영역
  • 프로세스가 수행 중인 동안에만 디스크에 일시적으로 저장하는 공간(휘발성)
  • 다수의 사용자 프로세스를 담을 수 있을 만큼 충분히 큰 저장공간이어야 하고 어느 정도의 접근 속도가 보장되어야 함
  • 프로세스가 종료되어 주소공간을 디스크로 내쫓는 것이 아니라, 특정한 이유로 수행 중인 프로세스의 주소 공간을 일시적으로 메모리에서 디스크로 내려놓는 것임
  • 디스크 → 메모리 : 스왑 인, 메모리 → 디스크 : 스왑 아웃
• 과정
  1. 스와퍼라고 불리는 중기 스케줄러가 스왑아웃시킬 프로세스 선정
  2. 선정된 프로세스에 대해 현재 메모리에 올라가 있는 주소 공간의 내용을 통째로 디스크 스왑 영역에 스왑 아웃
  3. 남아있는 프로그램이 충분히 실행되고 나면, 다시 스왑 아웃되었떤 프로그램을 올림
• 프로그램의 물리적 주소가 변하지 않는 컴파일 타임 바인딩, 로드 타임 바인딩 방식에서는 스왑아웃된 프로세스가 다시 스왑 인 될 때 원래 존재하던 메모리 위치로 다시 올라와야 함
• 프로그램의 물리적 주소가 변할 수 있는 실행시간 바인딩 방식에서는 추후 빈 메모리 영역 아무곳에나 프로세스를 올리면 됨

물리적 메모리의 할당 방식

• 프로세스를 메모리에 올리는 방식에 따른 분류

1. 연속할당 (contiguous allocation) : 각 프로세스를 물리적 메모리의 연속적 공간에 올리는 방식
   • 메모리를 분할하는 방식(분할을 관리하는 방식)에 따라 고정분할, 가변분할
2. 불연속할당 (noncontiguous allocation) : 하나의 프로세스를 물리적 메모리의 여러 영역에 분산해 적재하는 방식
   • 프로세스를 분할하는 방식에 따라 페이징, 세그멘테이션, 페이지드 세그멘테이션

연속할당

• 메모리를 분할하는 방식에 따른 분류

1. 고정분할 방식 : 물리적 메모리를 고정된 크기의 분할로 미리 나누어두는 방식
   • 물리적 메모리를 주어진 개수만큼의 영구적인 분할로 미리 나누어두고 각 분할에 하나의 프로세스를 적재
   • 분할의 크기는 모두 동일하게 할 수도 있고 서로 다르게 할 수도 있음
   • ❌ 하나의 분할엔 하나의 프로그램만 적재가능하기 때문에 동시에 메모리에 올릴 수 있는 프로그램의 수가 고정되어 있음
   • ❌ 수행 가능한 프로그램의 최대 크기도 제한되어 있음
   • ❌ 외부조각(프로그램의 크기 > 분할의 크기)과 내부조각(프로그램의 크기 < 분할의 크기)이 발생
2. 가변분할 방식 : 분할을 미리 나누어놓지 않고, 프로그램이 실행되고 종료되는 순서에 따라 분할을 관리하는 방식
   • 메모리에 적재되는 프로그램의 크기에 따라 분할의 크기, 개수가 동적으로 변하는 방식
   • ✅ 분할의 크기를 프로그램의 크기보다 크게 할당하지 않기 때문에 내부조각 발생 x
   • ❌ 이미 메모리에 존재하는 프로그램이 종료될 경우 중간에 빈 공간이 발생하게 되므로 외부조각은 발생할 수 있음
   • 크기가 n인 프로세스를 메모리에 올릴 때 물리적 메모리 내 가용 공간(메모리에 산발적으로 존재하는 빈공간) 중 어떤 위치에 올릴 것인가?
   1. 최초적합 (first-fit) : 크기가 n이상인 가용 공간 중 가장 먼저 찾아지는 곳에 프로세스 할당
      ✅ 가용 공간을 모두 탐색하지 않아도 되므로 시간적 측면에서 효율적
   2. 최적적합 (best-fit) : 크기가 n이상이면서 가장 작은 가용 공간에 프로세스 할당
      ✅ 공간적 측면에서 효율적
      ❌ 가용 공간들이 크기순으로 정렬되어 있지 않은 경우, 모든 가용공간을 탐색해야 하므로 시간적 오버헤드 발생
      ❌ 다수의 매우 작은 가용 공간들이 생성될 수 있음
   3. 최악적합 (worst-fit) : 가장 크기가 큰 곳에 새로운 프로그램 할당
      ❌ 최적적합과 마찬가지로 모든 가용 공간들을 탐색해야 하는 오버헤드 발생
      ❌ 상대적으로 더 큰 프로그램을 담을 수 있는 가용 공간을 빨리 소진한다는 문제점

• 컴팩션 (compaction) : 가용 공간들을 한쪽으로 모아서 하나의 큰 가용 공간을 만드는 방법
  • ✅ 외부조각 문제를 해결
  • ❌ 현재 수행 중인 프로세스의 메모리상 위치를 상당부분 이동시켜야 하므로 비용이 많이 듬
  • ❌ 수행 중인 프로세스의 물리적 위치를 옮기는 것이므로 실행시간 바인딩 방식이 지원되는 환경에서만 가능

불연속할당

• 프로세스를 분할하는 방식에 따른 분류

1. 페이징 : 각 프로세스의 주소 공간을 동일한 크기의 페이지로 잘라 페이지 단위로 적재시키는 방식
2. 세그멘테이션 : 코드, 데이터, 스택 등 의미 있는 단위인 세그먼트로 나누어 세그먼트 단위로 적재시키는 방식
3. 페이지드 세그멘테이션 : 세그먼트 하나를 다수의 페이지로 구성하는 방식

페이징 기법

• 일부는 스왑 영역에, 일부는 물리적 메모리에 혼재시킬 수 있음
• 물리적 메모리를 페이지와 동일한 크기의 프레임으로 미리 나누어둠 ⇒ 메모리에 올리는 단위가 동일한 크기의 페이지 단위이므로, 어떤 위치이든 사용될 수 있기 때문
• ✅ 연속할당에서 발생했던 동적메모리 할당 문제(최초적합, 최적적합, 최악적합)가 발생하지 않는다는 장점
• 하나의 프로세스여도 페이지 단위로 물리적 메모리에 올라가는 위치가 상이하므로, 주소 변환 절차가 연속할당보다 복잡
• 특정 프로세스의 몇 번째 페이지가 물리적 메모리의 몇 번째 프레임에 들어있다는 페이지별 주소 변환 정보를 유지하고 있어야 함 ⇒ 페이지 테이블
• ✅ 프로세스의 주소 공간과 물리적 메모리 모두 같은 크기의 페이지 단위로 나누기 때문에 외부조각 발생 x
• ❌ 프로그램의 크기가 항상 페이지 크기의 배수가 된다는 보장이 없기 때문에 내부조각은 발생가능

주소 변환 기법

• CPU가 사용하는 논리적 주소를 페이지 번호(p)와 페이지 오프셋(d)으로 나누어 주소변환
• 페이지 번호(p) : 각 페이지별 주소 변환 정보를 담고 있는 페이지 테이블 접근 시 인덱스, 해당 인덱스의 항목에는 그 페이지의 물리적 메모리상 기준 주소(시작 위치)가 저장됨
• 페이지 오프셋(d) : 하나의 페이지 내에서의 변위, 기준 주소값에 변위를 더함으로써 요청된 논리적 주소에 대응하는 물리적 주소 얻을 수 있음

페이지 테이블의 구현

• 페이지 테이블 기준 레지스터 : 메모리 내에서의 페이지 테이블의 시작 위치를 가리킴
• 페이지 테이블 길이 레지스터 : 페이지 테이블의 크기
• 페이징 기법에서는 두 번의 메모리 접근이 필요 : 주소 변환을 위해 페이지 테이블에 접근하는 것, 변환된 주소에서 실제 데이터에 접근하는 것 ⇒ 오버헤드 발생

• TLB (Translation Look-aside Buufer) 고속의 주소 변환용 하드웨어 캐시
  • 페이지 테이블 접근 오버헤드를 줄이고 메모리 접근 속도를 향상시키기 위해 사용
  • 가격이 비싸기 때문에 모든 정보를 담을 수 없고, 빈번히 참조되는 페이지에 대한 주소변환 정보만 담음
  • 주소 변환 정보는 프로세스별로 다 다르기 때문에 문맥교환 시 이전 프로세스의 주소 변환 정보를 담고 있던 TLB 내용은 모두 지워야 함
• 페이지 테이블 vs TLB
  • 페이지 테이블 : 하나의 프로세스를 구성하는 모든 페이지에 대한 주소 변환 정보가 페이지 번호에 따라 순차적으로 들어있음
  • TLB : 모든 페이지에 대한 주소 변환정보를 가지고 있지 않기 때문에 페이지 번호와 이에 대응하는 프레임 번호가 쌍으로 저장되어야 함
  • ❌ 해당 페이지에 대한 주소 변환 정보가 TLB에 있는지 확인하기 위해 모든 항목을 다 찾아봐야 하는 오버헤드 발생 ⇒ 병렬탐색이 가능한 연관 레지스터를 사용

계층적 페이징

• 수행 중인 프로세스가 증가함에 따라 전체 메모리의 상당 부분이 주소 변환을 위한 페이지 테이블에 할애되어 실제로 사용 가능한 메모리 공간이 줄어듦 ⇒ 메모리 낭비를 줄이기 위해 2단계 페이징 기법 사용
• 2단계 페이징 기법 : 외부 페이지 테이블 (outer page table) + 내부 페이지 테이블 (inner page table)
  • 사용되지 않는 공간에 대해서 외부 페이지 테이블의 항목을 NULL로 설정하여 대응하는 내부 페이지 테이블 생성 x
  • ✅ 1단계 페이징 기법에 비해 메모리의 낭비를 줄일 수 있음
  • ❌ 주소 변환을 위해 접근해야 하는 페이지 테이블의 수가 증가하므로 시간적인 손해
  • 프로세스의 논리적 주소를 두 종류의 페이지 번호(p1, p2)와 페이지 오프셋(d)으로 구분
  • p1 : 외부 페이지 테이블의 인덱스
  • p2 : 내부 페이지 테이블의 인덱스
  • <p1, p2, d> : 외부 페이지 테이블로부터 p1만큼 떨어진 위치에서 내부 페이지 테이블의 주소를 얻고, 내부 페이지 테이블로부터 p2 만큼 떨어진 위치에서 요청된 페이지가 존재하는 프레임의 위치를 얻고, 마지막으로 해당 프레임으로부터 d만큼 떨어진 곳에서 원하는 정보에 접근
  • 메모리 접근에 의한 시간적 오버헤드를 줄이기 위해서는 TLB를 사용하는 것이 효과적 ⇒ 공간적 이득을 얻을 수 있는 동시에 시간적 효율성도 얻을 수 있음

역페이지 테이블

• 페이지 테이블은 모든 페이지에 대해 페이지 테이블 항목을 다 구성해야 하기 때문에 메모리 공간낭비가 심함 ⇒ 역페이지 테이블
• 역페이지 테이블 : 물리적 메모리의 프레임 하나당 페이지 테이블에 하나씩의 항목을 두는 방식, 논리적 주소가 아닌 물리적 주소에 대한 페이지 테이블을 만드는 것 ⇒ 각 프로세스마다가 아니라 시스템 전체에 페이지 테이블을 하나만 두는 방법
• 페이지 테이블의 각 항목 : 프로세스 번호 (pid) + 프로세스 내의 논리적 페이지 번호 (p)
• ❌ 요청이 들어온 페이지가 물리적 메모리에 존재하는지 판단하기 위해 페이지 테이블 전체를 다 탐색해야 하므로 비효율적
• ⇒ 일반적으로 메모리에 유지하는 대신 연관 레지스터에 보관해 테이블 전체 항목에 대한 병렬탐색을 가능하게 함

공유 페이지

• 공유 코드(재진입 가능 코드, 순수 코드) : 메모리 공간의 효율적 사용을 위해 여러 프로세스에 의해 공통으로 사용될 수 있도록 작성된 코드, 읽기 전용
• 공유 페이지 : 공유 코드를 담고 있는 페이지
  • 여러 프로세스에 의해 공유되는 페이지이므로 물리적 메모리에 하나만 적재되어 메모리를 좀 더 효율적으로 사용할 수 있게 함
  • 모든 프로세스의 논리적 주소 공간에 동일한 위치에 존재해야 함
• 사유 페이지 : 프로세스별로 독자적으로 사용하는 페이지, 해당 프로세스의 논리적 주소 공간 중 어떠한 위치에 있어도 무방

메모리 보호

• 페이지 테이블의 각 항목에는 주소 변환 정보뿐 아니라 메모리 보호를 위한 보호비트와 유효-무효 비트를 둠
• 보호비트 (protection bit) : 각 페이지에 대한 접근 권한의 내용
  • 누구에 해당하는 접근 권한이 아닌 어떠한 접근을 허용하는지의 정보 (읽기/쓰기/읽기전용)
• 유효-무효 비트 (valid-invalid bit) : 해당 페이지의 내용이 유효한지에 대한 내용
  • 유효 : 해당 메모리 프레임에 그 페이지가 존재함, 접근 허용
  • 무효 : 프로세스가 그 주소 부분을 사용하지 않거나, 해당 페이지가 물리적 메모리에 올라와 있지 않고 스왑영역에 존재해 해당 메모리 프레임에 유효한 접근권한이 없다는 뜻

세그먼테이션

• 세그먼테이션 : 프로세스의 주소 공간을 동일한 크기로 나누는 것이 아니라 의미 단위의 세그먼트로 나누는 것
• 논리적인 단위로 나눈 것이기 대문에 크기가 균일하지 않음 ⇒ 부가적인 관리 오버헤드 발생
• <세그먼트 번호, 오프셋>
  • 세그먼트 번호 : 해당 논리적 주소가 프로세스 주소 공간 내에서 몇 번째 세그먼트에 속하는지
  • 오프셋 : 그 세그먼트 내에서 얼마만큼 떨어져 있는지
• 세그먼트 테이블 : 주소 변환을 위해 사용하는 테이블, 기준점 + 한계점
  • 기준점 : 물리적 메모리에서 그 세그먼트의 시작 위치
  • 한계점 : 그 세그먼트의 길이 (균일하지 않으므로 길이정보도 함께 보관)
  • 세그먼트 테이블 기준 레지스터 (STBR) : 현재 CPU에서 실행 중인 프로세스의 세그먼트 테이블이 메모리의 어느 위치에 있는지 그 시작주소를 담고 있음
  • 세그먼트 테이블 길이 레지스터 (STLR) : 그 프로세스의 주소 공간이 총 몇 개의 세그먼트로 구성되는지, 즉 세그먼트의 개수
• 논리적 주소를 물리적 주소로 변환하는 과정
  1. 요청된 세그먼트 번호가 STLR보다 작은지 확인 ⇒ 크다면 예외 발생시킴
  2. 논리적 주소의 오프셋이 그 세그먼트의 길이보다 작은지 확인 ⇒ 크다면 예외 발생시킴
  3. 위 2가지 경우를 모두 만족할 때만 주소 변환 작업 이루어짐
• 페이징 기법과 마찬가지로 각 항목에 보호비트와 유효비트를 둠
• 여러 프로세스가 특정 세그먼트를 공유해 사용하는 공유 세그먼트 지원, 역시 모든 프로세스의 주소 공간에서 동일한 논리적 주소에 위치해야 함
• ✅ 의미 단위로 나누기 때문에 공유와 보안의 측면에서 페이징 기법보다 효과적
• ❌ 세그먼트의 길이가 균일하지 않기 때문에 외부조각 발생가능
• ❌ 세그먼트를 어느 가용 공간에 할당할 것인지 결정하는 문제 (최초적합, 최적적합)

페이지드 세그먼테이션

• 페이지드 세그먼테이션 : 페이징과 세그먼테이션의 장점만을 취하는 주소 변환 기법
• 프로그램을 의미 단위의 세그먼트로 나눔, 단 세그먼트가 임의의 길이를 가질 수 있는 것이 아니라 반드시 동일한 크기 페이지들의 집합으로 구성되어야 함
• 물리적 메모리에 적재하는 단위는 페이지 단위

⇒ ✅ 하나의 세그먼트 크기를 페이지 크기의 배수가 되도록 함으로써 외부조각 문제 해결

⇒ ✅ 세그먼트 단위로 프로세스 간 공유나 보호가 이루어지므로 페이징 기법의 약점 해소

• 두단계 페이지 테이블 : 외부의 세그먼트 테이블 + 내부의 페이지 테이블
• <세그먼트 번호, 오프셋>
  1. 먼저 논리적 주소의 상위 비트인 세그먼트 번호를 통해 세그먼트 테이블의 해당 항목에 접근 ⇒ 여기에는 세그먼트의 길이와 그 세그먼트의 페이지 테이블 시작 주소가 들어 있음
  2. 세그먼트의 길이와 오프셋을 비교해 세그먼트의 길이를 넘어서는 메모리 접근 시도인지 여부 체크
  3. 오프셋을 상위/하위 비트로 나누어 상위비트는 세그먼트 내의 페이지 번호로 사용, 하위비트는 페이지 내에서의 변위로 사용
  4. 1에서 해당 세그먼트의 페이지 테이블 시작위치를 얻었으므로 그 위치에서 페이지 번호만큼 떨어진 항목으로부터 물리적 메모리의 페이지 프레임 위치를 얻음
  5. 이 위치에서 오프셋의 하위 비트값인 페이지 내 변위만큼 떨어진 곳이 바로 원하는 물리적 메모리 주소