[운영체제] 8. 메모리 관리
해당 내용은 공룡책(Operating System Concepts 10th Ed: Abraham Silberschatz, Peter Baer Galvin, Greg Gagne)과 대학 강의를 기반으로 재구성하여 정리한 공부 내용입니다.
+) 6장부터는 사자책(명품 운영체제: 황기태)에 더 중점을 두고 전개됩니다.
1. 메모리 계층 구조와 메모리 관리 핵심
메모리 계층 구조: CPU 레지스터 - 캐시 메모리 - 메인 메모리 - 보조 기억 장치 ...
읽기쓰기의 속도와 용량에 따라 계층 구조를 이루는 것
중심에 메인 메모리 존재!(일반적으로 메모리 = 메인 메모리 지칭)
메인 메모리(RAM): 휘발성, 하드 디스크: 비휘발성
메인 메모리 없이 컴퓨터 존재할 수 없음
CPU의 빠른 명령 처리 속도와 메모리 응답 속도의 차이 문제
→ CPU가 명령과 데이터를 가져오는 메모리 액세스 시간을 단축시켜야 하는 문제 (메모리 계층 구조의 목적!)
→ 메인 메모리보다 빠른 캐시 메모리를 CPU와 메인 메모리 사이에 설치해 사용
캐시 메모리: CPU가 현재 실행하는 프로세스 코드와 데이터 중 당장 실행할 일부를 메인 메모리에서 가져다 실행
일부만 두는 데도 효과적인 이유 → 참조의 지역성 때문
지역성의 두 종류:
1) 시간적 지역성(Temporal Locality): 한 번 참조된 데이터는 가까운 미래에 다시 참조될 가능성이 높음
2) 공간적 지역성(Spatial Locality): 메모리의 특정 부분이 참조되면, 그 인접한 메모리 위치도 곧 참조될 가능성이 높음
하드 디스크나 SSD 같이 대용량이면서 값이 싼 보조 기억 장치를 메인 메모리의 연장된 저장 공간으로 활용
메모리 계층 구조 요소
1. CPU 레지스터
CPU가 현재 실행할 코드와 데이터, 다음에 실행할 몇 개의 코드와 데이터를 미리 저장할 목적
일반적으로 8~30개
레지스터 1개 크기 32비트
2. 캐시 메모리
주기억장치로 사용하고 있는 메인 메모리보다 더 빠른 메모리
CPU의 빠른 처리 속도를 맞추기 위해 도입됨
가격이 비싸 소량만 사용됨
응답 속도와 위치에 따라 여러 레벨로 나누어 사용 - 현대의 멀티 코어 CPU의 경우 코어별로 L1/L2, 공유하는 L3 캐시를 두는 식
3. 메인 메모리
현재 실행 중인 모든 프로세스 코드와 데이터, 읽고 쓰는 여러 파일들의 블록, 운영체제의 커널 코드와 데이터 저장되어 있음
(캐시 메모리에서 일부 복사하는 코드와 데이터는 사용자 프로그램과 커널 구분 없이 복사됨)
4. 보조기억장치
전원을 꺼도 지워지지 않는 대용량 저장 장치
메인 메모리 크기 한계로 인해 적재된 프로그램 코드와 데이터 일부를 일시 저장하는 용도(스왑 영역)로도 사용됨
프로그램 실행과 메모리 계층 구조
1. 운영체제가 보조기억장치에 저장된 실행 파일을 메인 메모리에 적재
2. 메인 메모리에 적재된 코드와 데이터 중 실행할 일부 코드와 실행에 필요한 데이터가 L3 캐시로 복사
3. L3 캐시에서 당장 실행할 코드와 데이터 일부가 L1/L2 캐시로 복사
4. CPU 코어가 L1/L2 캐시에서 현재 실행할 명령과 데이터를 레지스터로 읽어 들인 후 연산 실행
L1, L2, L3 캐시 모두 컴퓨터 시스템에 따라 존재 유무 다를 수 O
→ 캐시 없는 경우 CPU가 메인 메모리로부터 코드와 데이터를 액세스해 명령 실행
→ 캐시 있는 경우 CPU가 캐시로부터만 코드와 데이터를 읽고 실행 → 반드시 실행에 필요한 내용 캐시로 복사되어야 함
메인 메모리 ↔ 캐시
CPU가 현재 프로세스나 스레드 실행을 중단하고 다른 프로세스나 스레드 실행 시 L1/L2 캐시에는 새로 실행하고자 하는 프로세스나 스레드의 명령과 데이터를 찾을 수 없는 캐시 미스(cache miss) 발생 → 연쇄적으로 메인 메모리로부터 L3 캐시, L1/L2 캐시로 새 프로세스 코드와 데이터 이동. 그전에 현재 캐시에 들어 있는 데이터 중 수정된 데이터는 L3 캐시나 메인 메모리에 기록돼야 함
→ 캐시로 인해 프로세스나 스레드의 컨텍스트 스위칭이 코드와 데이터를 이동시키는 보이지 않는 오버헤드 초래
캐시 미스는 프로그램 실행 중에도 발생
메인 메모리 ↔ 보조기억장치
메인 메모리 전체가 사용 중이거나 빈 영역이 일정 이하로 줄어들면 메인 메모리에 적재된 코드나 데이터 일부를 하드디스크나 SSD에 저장해 공간을 확보하는 기법 → 가상 메모리
메모리 계층화가 효율적인 이유: 참조의 지역성(locality of reference)
: 코드나 데이터, 자원 등이 아주 짧은 시간 내에 다시 사용되는 프로그램의 특성
→ 빠른 캐시를 사용해 얻는 이득 > 캐시를 다시 채우기 위해 CPU가 대기하는 실
메모리 보호
프로세스 간 독립된 메모리 공간을 가지도록 보장해야 하며, 프로세스별 메모리 공간은 서로를 보호하고 병행 실행을 위해 여러 프로세스가 메모리에 적재되게 해야 함
base 레지스터와 limit 레지스터를 사용하여 보호 기법 제공
base 레지스터는 가장 작은 물리 메모리 주소 값을 저장하고, limit 레지스터는 주어진 영역의 크기를 저장한다.
CPU는 사용자 모드에서 만들어진 모든 주소와 레지스터를 비교하여 다른 사용자 프로그램 또는 운영체제의 메모리 공간에 접근하면 트랩을 발생시킨다.
주소가 base보다 크거나 같은지, base+limit보다 작은지 확인
메모리 관리
메모리를 운영체제에 의해 관리해야 하는 이유:
1. 여러 프로세스에 의해 사용되는 공유 자원으로, 프로세스가 임의의 메모리 영역을 사용하게 할 수 없기 때문 - 메모리 할당 관리 필요
2. 메모리를 보호하기 위함. - 사용 중인 메모리에 대해 프로세스 접근 제어 및 사용자 모드에서 커널 공간 접근 제어 위한 보호 기능
3. 메모리의 용량 한계를 극복하기 위함. - 메모리의 물리적 크기 한계를 극복하는 가상 메모리 같은 메모리 관리 정책 필요
4. 메모리 사용 효율을 높이기 위함. - 다중프로그래밍정도(DOM);운영체제가 메모리에 동시 적재하여 실행시키는 프로세스 개수 = 운영체제 메모리 관리 효율성을 나타내는 지표. 메모리 용량 대비 많은 프로세스를 실행시켜 시스템 처리율을 높여야 함
→ 기본적인 메모리 관리 기능: 할당과 보호 - 프로세스에 메모리 배분, 자신 영역 외 침범하거나 훼손하지 못하게 제어
메모리 주소
메모리는 오직 주소를 이용해서만 접근됨
1. 물리 주소: 실제 메모리 주소(하드웨어 주소); address bus에 연결됨.
2. 논리/가상 주소: 프로그램 내에서 사용되는 주소; 코드나 데이터(변수나 동적 할당 메모리)의 주소
CPU가 프로세스 실행 동안 다루는 모든 주소는 논리 주소이다.
커널도 논리 주소로 이루어져 커널 코드가 실행될 때에도 논리 주소가 물리 주소로 바뀌어야 한다.
논리 주소의 물리 주소 변환
메모리를 액세스하기 위해서는 논리 주소가 물리 주소로 바뀌어, 물리 주소가 물리 메모리에 전달되어야 한다.
(위 그림처럼) CPU가 논리 주소를 사용해 물리 메모리에 데이터를 저장하고자 하면, 이 명령을 실행하기 위해 논리 주소 4번지를 발생 → 주소 변환 하드웨어(MMU)에 의해 물리 주소로 변환 → 주소가 CPU 패키지 바깥으로 빠져 나가 물리 메모리에 전달
주소 변환 하드웨어 MMU(Memory Management Unit): 프로세스의 논리 주소와 물리 주소의 매핑 정보를 담은 매핑 테이블을 참고하여 논리 주소를 물리 주소로 변환한다.
메모리 관리 방식에 따라 다르게 구현되며, CPU 패키지 내에 구성된다.
매핑 테이블과 MMU 덕분에 컴파일러는 프로그램을 논리 주소로 컴파일하는 데 부담이 없고, 운영체제도 프로세스의 코드와 데이터를 물리 메모리 빈 곳 아무데나 할당하고 적재해도 되며, 프로그램 개발자도 응용프로그램이 어디에 적재될지 몰라도 된다.(알 수도 없다.)
동적 로딩
프로세스가 실행되기 위해서는 그 프로세스 전체가 미리 메모리에 올라와있어야 했지만, 메모리 공간의 효율적 이용을 위해 동적 로딩을 사용하면 각 루틴(함수)이 실제 호출되기 전까지는 메모리에 올라오지 않고 재배치 가능한 상태로 디스크에 대기하고 있다.
메모리에 있는 루틴이 다른 루틴을 호출하면 호출된 루틴이 메모리에 적재되어 있는지 조사하고, 안 되어 있다면 relocatable linking loader가 불려 요구된 루틴을 메모리에 가져온 뒤 변화를 테이블에 기록한다.
장점은 루틴이 필요한 경우에만 적재되는 것 → 오류 처리 루틴처럼 빈도가 낮은데 실행할 코드가 많은 경우에 유용
운영체제의 특별한 지원 필요 없지만, 동적 로딩을 구현하는 라이브러리 루틴을 제공해줄 수는 있다.
동적 링킹
링킹을 실행 시기까지 미룸
Static linking의 경우: 시스템 라이브러리와 사용자 코드가 로더에 의해 실행 파일 이미지 내에 통합
Dynamic linking의 경우: 코드와 라이브러리가 분리되어 있어 필요 시 로드됨
동적 링킹은 주로 시스템 라이브러리에 사용되어 메모리 낭비를 줄인다.
또한 공유된 시스템 라이브러리를 참조, 즉 이러한 라이브러리를 여러 프로세스 간에 공유할 수 있게 하여 패치나 보안 업데이트 적용도 용이하다. → 버전 관리 필요
(동적 링킹 라이브러리를 공유 라이브러리라고도 한다.)
스텁(stub): 프로그램이 실행될 때 동적 라이브러리에 있는 함수 호출을 처리하기 위해 사용되는 코드 조각
주로 PLT(Procedure Linkage Table)에 위치
PLT는 각 외부 함수 호출을 위한 stub 코드들의 집합이다.
프로그램이 동적 라이브러리 함수를 호출할 때 실제 주소를 찾을 수 있도록 지원한다.
함수의 첫번째 호출 시 동적 링커에 의해 실제 함수 주소를 찾아 GOT(Global Offset Table)에 저장
이후 호출 시에는 GOT에 저장된 실제 주소로 점프
동적 링커는 실행 파일이 로드될 때 NEEDED 정보를 참고해 필요한 라이브러리들을 메모리에 로드
로드 과정에서 라이브러리 내의 함수와 변수 심볼을 실행 파일의 심볼 테이블과 매칭함
MMU(memory management unit)
논리 주소를 물리 주소로 바꾸어 주는 하드웨어 장치
base 레지스터 = relocation 레지스터
동적으로 논리 주소에 재배치 레지스터 값을 더해 주소를 변환
물리 메모리 관리
메모리 할당
메모리 할당: 운영체제가 새 프로세스를 실행시키거나 실행중인 프로세스가 메모리를 필요로 할 때 프로세스에게 물리 메모리를 할당하는 것
1) 프로세스의 코드와 데이터를 적재하기 위한 공간 할당 2) 프로세스 실행 중 동적으로 스택이나 힙을 사용할 때 필요한 공간 할당
→ 전적으로 운영체제 커널에 의해 수행됨
명령어와 데이터를 메모리 주소로 주소 바인딩하는 것은 3개의 다른 단계에 발생할 수 있다.
Compile time: absoute code 생성 (메모리 위치가 바뀌면 재컴파일되어야 한다)
Load time: relocatable code 생성 (프로그램이 메모리에 적재될 때 실제 메모리 주소가 할당된다.)
Execution time: 실행 시간까지 바인딩을 지연. 주소 맵을 위한 하드웨어 지원이 필요하다.
컴파일 타임 및 로드 타임 바인딩 → 컴파일러와 링커에 의해 매겨진 주소
실행 타임 바인딩 → 가상 메모리 시스템으로, 운영체제가 메모리 보호 및 접근 제어를 담당
논리 주소와 물리 주소 분리 효과
1. 논리 주소 공간을 물리 주소 공간보다 크게 설정 가능:
사용 가능한 실제 메모리 크기를 초과하는 데이터와 코드 처리 가능
개발자가 실제 메모리 제약 없이 프로그램을 더 자유롭게 설계할 수 있음
2. 동적 메모리 할당 시 효율성:
프로세스가 물리적 메모리의 어떤 특정 위치에 구속받지 않고, 필요에 따라 어디에나 위치 가능
메모리 조각화 문제를 완화할 수 있으며, 물리 메모리 이용률을 최적화
3. 프로그램의 독립성:
논리 주소를 사용하여 프로그램은 물리적 메모리와 독립적으로 작동
개발자가 메모리 관리에 대한 복잡성을 신경 쓰지 않고 코드를 작성할 수 있음
운영체제의 메모리 할당 기법
연속 메모리 할당
연속 메모리 할당(contiguous memory allocation): 각 프로세스에게 메모리 한 덩어리씩 할당하는 기법
→ 프로세스가 할당받은 메모리가 한 덩어리로 연속된 공간임을 의미함
1) 고정 크기 할당(fixed size partition allocation)
: 메모리 전체를 파티션으로 불리는 고정 크기로 나누고, 프로세스마다 1개의 파티션을 할당하는 기법
= 고정 할당, 정적 할당이라고도 부름
파티션의 크기는 모두 같거나 다를 수 있다.
프로세스 크기에 가장 가까운 파티션을 할당한다.
메모리 전체를 n개의 동일한 크기의 파티션으로 분할해두고, 프로세스를 실행시킬 때 각 프로세스에게 1개의 파티션을 할당함
동시에 실행시킬 수 있는 프로세스 개수는 n개로 제한, 새로운 프로세스가 도착하면 작업 큐에서 대기해야 한다.
프로세스가 파티션 크기보다 작은 경우 메모리 일부가 낭비되는 문제(=내부 단편화)
파티션 크기보다 큰 프로세스는 처음부터 실행될 수 없는 문제
→ 시스템 운영자가 실행시킬 전체 응용프로그램들의 크기를 사전에 계산하여 파티션 크기를 정하는 방식으로 해결
(당시에 실행시킬 응용프로그램이 정해져 있었기에 가능한 방법이다.)
2) 가변 크기 할당(variable size partition allocation)
: 프로세스마다 프로세스와 동일한 크기의 메모리를 할당하는 기법
= 동적 할당이라고도 부름
파티션이 미리 나누어져 있지 않고 프로세스 크기나 요청에 따라 파티션 크기가 정해진다.
수용 가능한 프로세스의 개수가 가변적
프로세스가 도착했을 때 가용 메모리가 부족 → 실행 중인 프로세스가 종료되어 필요한 만큼 가용 공간이 생길 때까지 작업 큐에서 대기한다.
단편화(fragmentation)
단편화: 프로세스에게 할당할 수 없는 작은 크기의 조각 메모리(hole)들이 생기는 현상
위치에 따라 내부 단편화, 외부 단편화로 분류
어떤 메모리 정책을 사용해도 단편화는 발생 → 단편화로 인한 메모리 낭비를 줄이는 메모리 할당 정책 강구
내부 단편화
프로세스에게 할당된 메모리 영역 내에 활용할 수 없는 홀이 생기는 경우
고정 크기 파티션에서 발생
프로세스 크기와 파티션 크기의 차이만큼 내부에 홀이 발생 → 다른 프로세스에게 할당할 수 없는 낭비 메모리임
외부 단편화
할당된 메모리들 사이에 활용할 수 없는 홀이 생기는 경우
가변 크기 파티션에서 발생
외부 단편화로 인해 할당할 메모리가 부족해지면 파티션을 이동시켜 홀을 없애는 메모리 압축(memory compaction) 기법을 사용할 수 있다.
연속 메모리 할당 구현
하드웨어 지원
하드웨어적 구현이 필요한 부분:
1) 프로세스 실행 중 논리 주소를 물리 주소로 변환하는 기능
2) 프로세스가 다른 프로세스의 메모리 액세스를 금지하는 기능
구현을 위해 필요한 CPU 레지스터 및 장치:
- base 레지스터: 현재 실행 중인 프로세스에게 할당된 물리 메모리 시작 주소
- limit 레지스터: 현재 실행 중인 프로세스에게 할당된 메모리 크기
- 주소 레지스터: 현재 액세스하는 메모리의 논리 주소
- 주소 변환 하드웨어(MMU): CPU에서 나오는 논리 주소를 물리 주소로 변환하는 장치
명령 레지스터에 있는 명령을 실행하기 위해 논리 주소 300이 물리 주소로 변환되어야 함
→ CPU가 주소 레지스터에 담긴 논리 주소 300 출력 → MMU가 논리 주소를 limit 레지스터의 값과 비교해 할당된 메모리 범위 내인지 체크함(다른 프로세스 메모리 보호 위함) → 범위를 넘어서면 시스템 오류 신호를 발생시켜 CPU가 오류를 처리하는 커널 코드를 실행하고 현재 프로세스를 강제 중단 / 정상 범위이면 MMU가 'base 레지스터에 저장된 물리 주소 1000 + 주소 레지스터에 담긴 논리 주소 300 = 물리 주소 1300 생성하여 CPU 패키지 바깥으로 내보냄 → 물리 주소 1300이 주소 버스를 타고 메모리에 전달 → 메모리는 1300번지에 저장된 데이터를 데이터 버스에 내놓음 → CPU가 이 값을 CPU 내부로 전달
운영체제 지원
모든 프로세스에 대해 프로세스별로 할당된 물리 메모리의 시작 주소와 크기 정보를 저장 관리
비어 있는 메모리 영역 관리
→ 새 프로세스를 스케줄링하여 실행시킬 때마다 물리 메모리의 시작 주소와 크기 정보를 CPU 내부 base, limit 레지스터에 적재
홀 선택 알고리즘
hole selection algorithm = 동적 메모리 할당(dynamic memory allocation); 운영체제가 프로세스를 처음 실행시키거나 프로세스의 실행 도중 메모리가 요구될 때 적당한 홀을 선택해서 할당해야 한다.
고정 크기 할당 시: 홀들을 가용 메모리 리스트로 만들어 관리하고, 이중 하나를 선택하면 됨
가변 크기 할당 시: 메모리 전체에 있는 홀마다 시작 주소와 크기 정보를 구성하고, 이들을 홀 리스트(또는 가용 메모리 리스트)로 만들어 관리해야 함. 그리고 메모리 할당 요청이 발생하면 홀 리스트에서 적절한 홀을 선택해야 함. → 어떤 홀을 선택하느냐에 따라 성능이 상이하여 선택이 중요!
1. first-fit(최초 적합)
홀 리스트를 검색하여 처음으로 만나는, 요청 크기보다 큰(수용 가능한) 홀 선택
good: 알고리즘 속도는 빠름
bad: 외부 단편화로 인한 메모리 낭비 큼
2. best-fit(최적 적합)
홀 리스트를 검색하여 요청 크기를 수용하는 것 중 가장 작은 홀을 선택
good: 메모리 낭비 적음
bad: 홀 리스트가 크기별로 정렬되어 있지 않은 경우, 홀을 전부 검색해야 하는 부담이 존재
3. worst-fit(최악 적합)
홀 리스트를 검색하여 요청 크기를 수용하는 것 중 가장 큰 홀을 선택
bad: 홀 리스트가 크기별로 정렬되어 있지 않은 경우, 홀을 전부 검색해야 하는 부담이 존재
잘 사용하지 않음!
연속 메모리 할당의 장단점
good:
메모리 할당 알고리즘이 단순하여 구현이 용이
논리 주소를 물리 주소로 바꾸는 과정이 단순하여 CPU의 메모리 액세스 속도가 상대적으로 빠름(시작 위치, 크기 정보만 관리하면 됨)
bad:
프로세스에게 하나의 연속된 메모리를 할당하여 메모리 할당의 유연성이 부족하다.
메모리 전체에 비어 있는 작은 공간(홀)들을 합하면 충분한 공간이 있음에도 불구하고, 프로세스를 적재할 만큼은 연속된 메모리가 없어 프로세스를 적재할 수 없는 경우가 발생한다.
→ 분할 메모리 할당 기법으로 해결
→ 홀들을 한쪽으로 모아 큰 빈 메모리 공간을 만드는 메모리 압축 과정이 필요
처음부터 프로세스에게 필요한 메모리를 예측하여 큰 메모리를 할당한다면 내부 단편화를 초래하는 메모리 낭비가 생길 수 있다.
버디 시스템
오늘날 리눅스의 커널 메모리 관리에 사용되는 메모리 할당 알고리즘
메모리 할당과 반환 속도를 높이기 위해, 고정 크기 할당과 가변 크기 할당의 장점을 결합한 연속 메모리 할당 정책을 사용하는 것
분할 메모리 할당
분할 메모리 할당(non-contiguous memory allocation): 프로세스에게 필요한 메모리를 여러 덩어리로 나누어 분산 할당하는 기법
1) 가변 크기 할당 - 세그먼테이션(segmentation)
: 프로세스에게 크기가 다른 여러 개의 덩어리 메모리를 할당하는 기법.
프로세스를 여러 개의 논리적인 덩어리(=세그먼트)로 분할한다.
이때 각 덩어리가 세그먼트(segment)이다.
각 논리 세그먼트에 한 덩어리의 물리 메모리를 할당하는 정책이다.
세그먼트: 프로세스 내에서 하나의 단위로 다룰 수 있는 의미 있는 블록(논리 블록) ex. 함수, 객체
→ 프로세스를 구성하는 각 세그먼트들의 크기가 다를 수 밖에 없다.
프로세스를 구성하는 세그먼트들을 물리 메모리에 분산 할당(주로 코드, 데이터, 스택, 힙 4개 세그먼트로 분할)
코드 세그먼트 - 프로그램 전체에 걸쳐 작성된 모든 코드들을 모음
데이터 세그먼트 - 프로그램 전체에 걸쳐 선언된 전역 변수들과 정적 변수들을 모음
스택 세그먼트 - 함수가 호출될 때 지역 변수나 매개변수, 리턴값을 저장하는 메모리 공간
힙 세그먼트 - 프로세스가 실행 중에 동적으로 할당받는 메모리 영역
컴파일러와 링커, 로더의 도움이 필요
컴파일러와 링커 - 응용 프로그램과 라이브러리의 코드를 한 군데로 모아 코드 세그먼트를 구성시키고, 전역 변수들과 정적 변수들을 모아 데이터 세그먼트를 구성한 후 실행 파일을 생성한다.
로더 - 프로그램 실행 시 실행 파일 내에 구성되어 있는 각 논리 세그먼트에 대해 물리 메모리에서 동일한 크기로 물리 세그먼트를 할당하고, 논리 세그먼트를 물리 세그먼트에 적재한다.
운영체제는 프로세스 실행 시 필요한 크기의 스택 세그먼트와 동적 할당을 위한 힙 세그먼트를 물리 메모리에 할당한다.
논리 세그먼트와 물리 세그먼트의 매핑
세그먼트 테이블은 시스템 전체에 1개! 프로세스 당 세그먼트 개수가 작기 때문
현재 적재한 모든 프로세스들의 세그먼트들을 관리 → 논리 세그먼트 당 하나의 항목이 저장됨
항목은 논리 세그먼트가 적재된 세그먼트의 시작 물리 주소(base)와 세그먼트의 크기(limit)로 구성
프로세스가 실행되고 사라지는 과정이 반복되면서 자연스럽게 물리 세그먼트 사이에 홀 발생 → 외부 단편화 초래
새로운 프로세스 실행 시 프로세스의 각 세그먼트를 적재할 빈 홀을 찾기 위해 홀 선택 알고리즘을 사용
세그먼테이션의 구현
하드웨어 지원
- 논리 주소 구성: 프로그램에서 사용되는 논리 주소는 세그먼트 번호와 옵셋(세그먼트 내에서의 상대 주소)으로 구성
- CPU: CPU에 의해 발생되는 논리주소는 [세그먼트 번호, 옵셋] 형태. CPU에 세그먼트 테이블의 시작 주소를 가리키는 레지스터 필요
- MMU: 메모리 보호(논리 주소가 세그먼트 크기를 넘어서는지 판별)와 주소 변환(논리 주소를 물리 주소로 바꿈) 구현
CPU에서 논리 주소 발생 → 메모리에 저장된 세그먼트 테이블에서 세그먼트 번호에 해당하는 항목이 일단 읽힘 → 이 항목의 limit값과 논리 주소의 옵셋을 비교 → offset이 limit보다 크면 논리 주소가 세그먼트의 영역을 벗어난 것이므로 시스템 오류 발생 / offset이 limit보다 작으면 세그먼트 테이블의 항목에 들어 있는 물리 세그먼트 시작 주소 + 옵셋 = 물리 주소 출력
- 세그먼트 테이블: 세그먼트 테이블을 메모리에 두면 CPU가 논리 주소를 발생시켜 메모리를 액세스할 때마다 현재 세그먼트(s)의 limit과 base 값을 알아내기 위해 메모리에 있는 세그먼트 테이블 항목을 읽어와야 해서 실행 속도에 큰 부담이 됨. → 주소 변환 속도를 위해 세그먼트 테이블 일부를 MMU 내에 두기도 함
운영체제 지원
현재 할당된 물리 세그먼트들의 리스트와 홀 리스트 생성, 관리
세그먼트 테이블 생성, 유지, 관리
프로세스 생성마다 논리 세그먼트를 적재할 물리 세그먼트를 홀 리스트에서 찾아 할당하고, 프로세스가 종료할 때마다 할당된 물리 세그먼트를 반환하는 기능을 가져야 함
컴파일러, 링커, 로더 지원
사용자 프로그램을 사전에 정의된 세그먼트들로 분할하고 링킹
기계 명령에 들어가는 메모리 주소도 [세그먼트 번호, 옵셋] 형식으로 컴파일
실행 파일에 만들어진 논리 세그먼트들을 인지하고, 이들을 물리 메모리의 빈 영역을 할당받아 적재하여 세그먼트 테이블을 갱신함
단편화 문제
프로세스에 가변 크기로 물리 세그먼트들을 할당
논리 세그먼트와 동일한 크기의 물리 세그먼트를 할당 → 내부 단편화는 없음
But 세그먼트마다 크기가 서로 달라, 세그먼트들 사이에 빈 공간이 있을 때 크기가 작아 새 프로세스에 할당하지 못하는 메모리 낭비가 발생할 수 있다. → 외부 단편화 문제 → 페이징 기법 도입
2) 고정 크기 할당 - 페이징(paging)
: 프로세스에게 동일한 크기의 덩어리를 여러 개 할당하는 기법
프로세스를 논리적인 단위로 분할하지 않고, 논리 주소 0번지부터 페이지라고 부르는 고정 크기로 분할한다.
물리 메모리 역시 페이지와 동일한 크기로 분할(프레임 단위)하여, 프로세스의 각 페이지를 물리 메모리의 프레임에 하나씩 분산 할당한다.
페이징 메모리 관리
: 프로세스의 주소 공간을 0번지부터 페이지로 불리는 고정 크기로 나누고, 물리 메모리도 동일한 크기로 0번지부터 분할하여, 프로세스의 각 페이지를 물리 메모리의 임의의 페이지에 분산 할당하는 메모리 관리 기법
물리 메모리에서 페이지 크기의 메모리 블록을 프레임(=페이지 프레임, 물리 페이지)이라고 한다.
대부분 4KB로 설정된다.(8, 16KB도 존재)
- 프로세스 주소 공간을 페이지 크기로 일률적으로 나눔
- 페이지 경계를 고려하지 않고 코드, 데이터, 힙을 이어서 배치
- 페이지 테이블의 각 항목(PTE, Page Table Entry)에는 페이지 프레임 번호(물리 메모리에서 해당 페이지의 위치) 기록
- 프로세스마다 페이지와 물리 프레임을 매핑하는 페이지 테이블 존재
- MMU 장치가 페이지 테이블을 이용해 논리 주소를 물리 주소로 변환
장점
1. 구현이 쉽다. 고정 크기 페이지로 분할하여 이해도 더 쉽다.
2. 이식성이 높다. CPU에 의존적이지 않다.
3. 융통성이 높다. 시스템에 따라 페이지 크기를 변경할 수 있다.
4. 세그먼테이션에서 발생하는 외부 단편화 존재X, 홀 선택 알고리즘 실행할 필요X → 메모리 활용, 시간 오버헤드 면에서 우수
내부 단편화가 발생하기는 함! 다만 크기가 매우 작음.
세그먼테이션과 페이징 기법은 서로 장단점이 있어 현대 컴퓨터 시스템에서는 페이징을 기반으로 세그먼테이션을 혼합 사용한다.
페이지 테이블
char *p = (char*)malloc(200); 을 실행한 경우:
프로세스 힙 영역에 페이지 5를 할당하고, 비어 있는 물리 프레임 2를 할당하여 프로세스 페이지 테이블 항목 5에 프레임 번호 2를 기록한다. 그리고 페이지 5의 앞 200바이트를 할당해준다.
malloc(200) 함수는 페이지 번호 5의 논리 주소인 20480을 리턴하여 포인터 변수 p에는 20480이 저장
페이지 5의 시작 주소는 5*4KB = 20KB = 20*1024 = 20480으로 계산된 주소
프레임 2의 물리 주소는 2*4KB = 8192번지이다.
이때 *p = 'a'; 실행 시 MMU에 의해 논리 주소 20480이 물리 주소 8192로 바뀌어 물리 메모리 8192번지에 'a'가 저장된다.
프로세스에서 시스템 호출을 실행하는 경우:
커널 공간에 있는 페이지 k의 커널 코드를 실행하는 경우 현재 프로세스의 페이지 테이블에서 물리 프레임 번호를 알아내어 이에 적재된 커널 코드를 실행하게 된다.
즉 커널 코드도 논리 주소로 되어 있다!
단편화
페이징에는 외부 단편화가 발생하지 않는다. 내부 단편화가 발생하지만, 스택이나 힙 영역에 할당된 메모리는 실행 중에 계속 변하므로 단편화 계산에서 배제한다면, 프로세스 코드나 데이터가 주소 공간에 연속되어 있으므로 내부 단편화는 마지막 페이지에만 생긴다. 즉 프로세스 당 단편화로 인해 낭비되는 메모리 평균 크기는 1/2페이지, 즉 2KB로 매우 작다.
페이지 크기가 커지면 단편화도 커지며, 프로세스를 구성하는 페이지 개수는 줄어들고, 페이지 테이블 크기도 작아진다.
페이징 주소 체계
페이징의 논리 주소
논리 주소 = [페이지 번호(p), 옵셋(offset)]
페이지 크기가 4KB(=2^12)라면, 페이지 내 각 바이트 주소(옵셋 주소)를 12비트로 나타낼 수 있다. = 옵셋 크기는 12비트
32비트의 논리 주소에서 하위 12비트는 페이지 내 옵셋 주소, 상위 20비트는 페이지 번호가 된다.
논리 주소의 물리 주소 변환
p를 페이지 테이블의 인덱스로 하여 페이지 테이블 항목을 찾음 → 페이지 p가 할당된 프레임 번호 f 획득 → 프레임 번호 f에 대해 옵셋을 그대로 사용하면 물리 주소가 된다.
* 페이지 테이블은 물리 메모리에 저장된다는 것을 잊지 말 것
페이징의 구현
CPU와 MMU, 운영체제의 지원이 필요하다.
하드웨어 지원
CPU 칩 내에 현재 실행 중인 프로세스의 페이지 테이블이 적재된 물리 메모리 주소를 가진 레지스터, PTBR(Page Table Base Register)가 필요하다.
레지스터의 값은 PCB에 저장된다.
논리 주소를 물리 주소로 변환하기 위한 MMU 장치가 CPU 칩에 패키징되며, CPU에 따라 페이징 테이블 일부를 MMU 장치 내에 저장하기도 한다.
Page-table base register(PTBR): 페이지 테이블을 가리키는 포인터
Page-table length register(PTLR): 페이지 테이블의 사이즈를 표현
→ 이 두 레지스터를 MMU가 관리
PCB가 테이블 관련 레지스터를 다른 레지스터드롸 함께 보관하다가, 문맥 전환 시 테이블 레지스터 값들을 MMU로 전달
운영체제 지원
물리 메모리의 빈 프레임 리스트를 생성, 관리, 유지하여 메모리 프레임을 동적으로 할당/반환하는 기능
이에 따라 페이지 테이블을 관리하는 기능
각 프로세스마다 PCB에 주소 저장, 실행될 때마다 PTBR 레지스터에 옮기는 기능
페이지 테이블의 문제점과 TLB
1) 페이지 테이블로 인한 성능 저하
2) 공간 낭비
1) 페이지 테이블은 크기 때문에 메모리에 두게 되어 CPU가 메모리를 액세스할 때마다 물리 메모리를 2번 액세스하여 실행 속도를 심각하게 저하시킨다.
2) 페이지 테이블의 크기는 프로세스의 최대 크기(주소 공간)에 맞추어 생성되지만 실제 프로세스 크기는 그에 못 미치므로 페이지 테이블이 많이 비어 있어 메모리 낭비를 가져온다.
1) 2번의 물리 메모리 액세스 문제 해결: TLB의 사용
메모리 액세스 = 페이지 테이블 항목 읽기 1번 + 데이터 액세스 1번
→ 페이지 테이블을 읽어오는 과정을 없애면 된다.
TLB
Translation Look-aside Buffer (=주소 변환용 캐시)
CPU가 최근에 액세스한 페이지 번호가 페이지가 적재된 프레임 번호의 쌍을 저장하는 캐시 메모리
MMU 내에 둔다.
TLB의 항목 = [페이지 번호 p, 프레임 번호 f]
일반 메모리와 달리, 페이지 번호를 모든 항목과 동시에 비교하여 프레임 번호를 출력한다.
→ 주소 번지를 사용하지 않고, 내용을 직접 비교하여 찾는 메모리라 하여 '내용-주소화 기억 장치(content addressable memory, CAM)', '연관 메모리(associative memory)'라고도 부른다.
상용 CPU 내 TLB의 경우 가격이 비싸고 공간 제약 때문에 64~1024개 정도로 작은 편이다.
→ 페이지 테이블 전체를 저장할 수 없고, 최근 액세스한 소수의 페이지와 프레임 번호를 저장하여 활용성을 높인다.
TLB를 활용한 메모리 액세스
TLB를 사용하는 경우 TLB 히트가 일어나면 바로 주소 변환 발생 → 1번만 물리 메모리를 액세스해 액세스 시간을 반으로 줄임
동일한 페이지를 연속해서 액세스하는 동안 TLB 히트가 바로 발생하므로 실행 속도가 대폭 향상된다.
단, 모든 프로그램의 실행 속도가 개선되는 것은 아님!
순차 메모리 액세스 패턴을 가진 프로그램에 매우 효과적
프로그램은 참조의 지역성을 띄는데, 이 경우 효과적이지만, 랜덤하게 메모리를 액세스할 경우 TLB 미스가 자주 발생할 것이다.
* 참조의 지역성(locality of reference): 프로그램이 실행되는 동안 짧은 시간 범위 내에 일정 구간의 메모리 영역을 반복 액세스하는 경향성
TLB 성능 = TLB 히트율 = TLB 히트 횟수 비율 / CPU 메모리 액세스 횟수
TLB의 항목 수와 페이지 크기에 비례 → 항목 수를 늘린다면 비용 상승, 페이지 크기를 늘리면 내부 단편화 증가로 메모리 낭비
→ 적절한 선택이 필요
TLB 도달 범위(TLB reach): TLB 캐시의 항목 수 * 페이지 크기로 계산 (성능 지표가 된다.)
실질 메모리 접근 시간(effective memory access time, EAT): hit ratio*메인 메모리 접근 시간+(1-hit ratio)*데이터 접근 시간
메모리 보호
보호 비트를 이용해 읽기 전용 페이지에 쓰기 작업이 이뤄지지 않도록 함 → 무효 비트가 설정된 페이지에서 매핑 시도 시 트랩 발생
page-table length register(PTLR)이 페이지 범위 넘어서는 접근을 방지하는 방법도 있음 → 모든 논리 주소 값을 PTLR과 비교해 오류가 나면 트랩 발생
2) 페이지 테이블의 낭비 문제 해결: 역페이지 테이블, 멀티레벨 페이지 테이블
페이지 테이블로 메모리가 낭비되는 2가지 요인
- 페이지 테이블의 일부 항목만 사용
- 프로세스마다 페이지 테이블 존재
32비트 주소 체계를 사용하는 경우 프로세스의 주소 공간은 4GB, 페이지가 4KB면 최대 페이지 개수는 100만개이다.
페이지 테이블 항목이 4바이트이면 프로세스의 페이지 테이블 크기는 4MB이다.
그러나 실제 크기가 10MB라면 프로세스를 위해 실제 활용되는 페이지 테이블 항목 수는 2560개이다.
또한 100개의 프로세스가 실행 중이면 페이지 테이블로만 소모되는 메모리가 100*4MB=400MB이다.
역 페이지 테이블
프레임을 중심으로 물리 메모리의 전체 프레임에 대해 각 프레임이 어떤 프로세스의 어떤 페이지에 할당되었는지 나타내는 테이블
시스템에 1개