[OS] 04. Main Memory

Background

메모리 : 각각 주소가 할당된 일련의 워드 또는 바이트로 구성

CPU는 PC(Program Counter)가 지시하는 주소에서 다음 명령어를 가져옴

해당 명령어는 필요시, 추가 데이터를 가져오거나 데이터를 메모리로 내보낼 수도 있음

 

명령어 실행 절차

1. 메모리로부터 하나의 명령어를 가져옴
2. 가져온 명령어를 해독 -> 메모리에서 피연산자를 가져옴
3. 명령어를 실행 / 필요시, 실행 결과를 메모리에 다시 저장

프로그램은 실행되기 위하여 비휘발성 저장장치에서 메모리로 가져와야 함 (프로세스)

메인 메모리와 레지스터는 CPU가 직접적으로 접근할 수 있는 유일한 저장장치
메모리 유닛은 ‘주소+읽기 요청’ 또는 ‘주소+데이터’ 그리고 쓰기 요청만 인식
레지스터 접근은 한 번의 CPU 클럭(or less)에 수행될 수 있음
메인 메모리 접근은 많은 사이클이 필요 -> stall이 발생 (지연) - 캐시는 메인 메모리와 CPU 레지스터 사이에 위치
올바른 작동 보장을 위해 메모리 보호가 필요

---

Base and Limit Register

컴퓨터 성능 향상을 위해 메모리에 여러 프로세스들이 동시에 유지되어야 함
시스템이 올바르게 동작하기 위해서는 사용자 프로그램으로부터 OS 영역이 보호되어야 함 (커널 영역 보호)

프로그램은 실행을 위해 메모리로 옮겨져 독립된 공간에 위치 / 각 프로세스는 분리된 메모리 공간을 확보
Base Register와 Limit Register는 물리 메모리 내의 프로세스 주소 공간을 결정하는데 사용됨

프로세스가 접근할 수 있는 메모리 주소 영역 설정

• Base Register (기준 레지스터) : 가장 작은 물리 메모리 주소를 가짐
• Limit Register (상한 레지스터) : 프로세스 주소 공간의 크기를 저장

CPU는 사용자 모드에 생성된 모든 메모리 접근을 확인하여 사용자의 Base와 Limit 사이에 위치하는지 확인해야 함

---

Address Binding

프로그램이 실행되기 위해 메모리로 가져와지면, Input Queue(입력 큐)를 형성
주소는 프로그램의 수명 주기의 다른 단계에서 다른 방식으로 표현

• 소스 코드는 기호(symbol)를 사용 : int A
• 컴파일 코드는 재배치 가능한 주소에 바인딩 : “이 모듈의 시작부터 14바이트”
• 링커, 로더는 재배치 가능한 주소를 절대 주소에 바인딩 : 74014
• 각 바인딩은 한 주소 공간을 다른 공간에 매핑

명령어와 데이터의 주소 바인딩은 3가지의 단계에서 발생

• Compile Time : 메모리 위치가 사전에 알려진 경우, 절대 코드(Absolute Code)를 생성이 시작 위치가 변경되면 다시 컴파일해야 함
• Load Time : 메모리 위치가 Compile Time에 알려지지 않은 경우 재배치 가능한 코드(Relocatable Code)를 생성
• Execution Time : 프로세스가 실행 중에 현재 메모리 세그먼트에서 다른 곳으로 이동할 수 있는 경우 Run Time까지 바인딩은 지연됨 / 주소 맵을 위한 하드웨어가 필요 (Base and Limit Register)

 

Logical Address Space

프로그램에 의해 생성된 모든 논리적 주소의 집합

 

Physical Address Space

프로그램에 의해 생성된 모든 물리적 주소의 집합

 

논리적 주소 공간은 별도의 물리적 주소 공간에 바인딩

• Logical Address : CPU에 의해 생성, Virtual Address라고도 불림
• Physical Address : 메모리 유닛에서 볼 수 있는 주소

 

 

컴파일 시간 및 로드 시간 주소 바인딩 방식은 논리 주소와 물리 주소가 동일
실행 시간 주소 바인딩 방식은 논리 주소와 물리 주소가 다름

 

Memory-Management Unit (MMU)

• 실행 시간에 가상(논리) 주소를 물리 주소로 매핑하는 하드웨어 장치
• 재배치 레지스터의 값은 메모리로 전송될 때, 사용자 프로세스에 의해 생성된 모든 주소에 추가됨
• Base Register : Relocation Register
• 사용자 프로그램은 논리 주소를 처리, 실제 물리 주소는 볼 수 없음
• 실행 시간 바인딩은 메모리의 위치에 참조가 발생할 때 일어남

Dynamic Loading

• 루틴은 호출될 때까지 로드되지 않음 (루틴 : Dynamic Loading으로 불러오는 것)
• 메모리 공간 효율성이 좋음 / 사용되지 않는 루틴은 로드되지 않음
• 모든 루틴은 재배치 가능한 형식으로 디스크에 유지
• 드물게 발생하는 경우를 처리하기 위해 많은 양의 코드가 필요할 때 유용함

Static Linking

• 시스템 라이브러리와 프로그램 코드가 로더에 의해 이진 프로그램 이미지로 결합

Dynamic Linking

• 실행 시간까지 Linking이 연기됨
• 적절한 메모리에 상주하는 라이브러리 루틴을 찾기 위해 사용되는 작은 코드 조각(Stub_스텁)을 사용
• 스텁(Stub)은 자신을 루틴의 주소로 대체하고 루틴을 실행
• OS는 루틴이 프로세스의 메모리 주소에 있는지 확인
• 메모리 공간에 없으면 메모리 공간에 추가
• 시스템 라이브러리를 수정하는 경우에 적용

---

Memory Allocation

고정 분할 기법

• 메모리를 동일한 크기의 파티션으로 분할
• 하나의 프로세스는 하나의 파티션에 할당
• 구현/관리는 쉬우나 제약이 많음 -> 요즘은 사용 X

가변 분할 기법

• OS는 어느 부분이 사용되는지 어느 부분이 가용 공간인지를 테이블로 관리
• OS는 가용 공간에 프로세스를 할당
• OS는 항상 가용 공간의 크기와 입력 큐를 유지해야 함

Contiguous Allocation (Fixed / Variable)

• 메인 메모리는 OS와 사용자 프로세스 모두를 지원
• 메인 메모리는 일반적으로 2개의 파티션으로 분할
• Resident OS는 보통 인터럽트 벡터와 함께 낮은 메모리에 저장
• 사용자 프로세스는 높은 메모리에 저장
• 각 프로세스는 메모리의 단일 연속적인 영역에 포함
• Reallocation 레지스터는 사용자 프로세스 사이의 서로를 보호하고 OS 코드와 데이터를 변경하는데 사용
• Base 레지스터는 가장 작은 물리적 주소값을 포함
• Limit 레지스터는 논리적 주소의 범위를 포함, 각 논리적 주소는 Limit 레지스터보다 작아야 함
• MMU는 논리적 주소를 동적으로 매핑

Multiple-partition Allocation

• 멀티프로그래밍의 정도는 파티션의 개수로 제한
• 효율성을 위해 가변 파티션 크기를 사용 (Variable-partition size)
• Hole : 사용가능한 메모리 블록 / 다양한 크기의 Hole이 메모리에 흩어져 있음
• 프로세스가 도착하면 충분히 큰 Hole에 메모리를 할당받음
• 프로세스가 종료되면 파티션을 해제하고 인접한 빈 파티션과 합침
• OS는 ‘할당된 파티션’과 ‘비어있는 파티션(Hole)’의 정보를 유지

Dynamic Storage-Allocation Problem

• First-fit : 충분히 큰 첫 번째 Hole을 할당
• Best-fit : 충분히 큰 가장 작은 Hole을 할당 / 정렬되어 있지 않으면 전체 검색 필요 / 남는 Hole이 가장 작음
• Worst-fit : 가장 큰 Hole을 할당 / 전체 검색 필요 / 남는 Hole이 가장 큼

First-fit과 Best-fit이 Worst-fit보다 속도와 저장 효율성 측면에서 우수

 

Fragmentation (단편화)

• External Fragmentation -> Variable size Contiguous Allocation의 문제
• 전체 메모리 공간은 요구에 충족할 수 있지만 그 공간이 연속적이지 않음
• Internal Fragmentation -> Fixed size Contiguous Allocation의 문제
• 메모리가 요구보다 약간 크게 할당될 수 있음 / 이 크기 차이로 파티션이 사용되지 않을 수 있음
• First-fit 분석은 N개의 블록이 할당되면 0.5N개의 블록이 단편화로 손실 -> 50% 규칙, 1/3은 사용 불가능
• Compaction으로 External Fragmentation을 줄일 수 있음
• 메모리 내용을 섞어서 모든 Free 메모리를 한 블록에 위치시킴
• Compaction은 재배치가 동적일 때만 가능, 실행 시간에 수행되어야 함 / I/O 문제를 일으킬 수 있음

---

Segmentation

메모리의 사용자 관점을 제공하는 메모리 관리 방법

세그먼트의 크기는 같지 않음

프로그램은 세그먼트의 집합임

세그먼트 : 논리적 유닛 (Main program, Procedure, Function, Method, Object, Variables, Stack, Arrays 등)

 

Segmentation Architecture

• 논리적 주소 : <Segment-Number, Offset>
• Segment Table : 물리 주소를 매핑
   - base : 세그먼트가 메모리에 위치하는 시작 물리 주소를 포함
   - limit : 세그먼트의 길이를 지정
• Protection : 각 세그먼트 테이블에 추가 가능
   - 유효성 비트(validation bit) = 0이면, 불법 세그먼트 / Read, Write, Execute 권한 지정 가능
   - 보호 비트는 세그먼트와 관련, 코드 공유는 세그먼트 레벨에서 발생
• 세그먼트의 길이는 다양하므로 메모리 할당은 Dynamic Storage-Allocation 문제 (External Fragmentation 발생)

---

Paging

프로세스의 물리 주소는 연속적이지 않을 수 있음

페이지의 크기는 모두 같음
External Fragmentation 방지 / 다양한 크기의 메모리 Chunks 문제 방지
물리 메모리를 고정된 사이즈의 블록 "Frames"으로 나눔 (크기는 512bytes ~ 16Mbytes)

논리 메모리를 같은 사이즈의 블록 "Pages"로 나눔
모든 빈(Free) 프레임을 추적 / 페이지 테이블은 각 프로세스별로 생성
크기가 N인 페이지의 프로그램을 실행시키기 위해, N개의 빈(Free) 프레임을 찾고 로드
논리 주소를 물리 주소로 변환하기 위해 Page Table을 설정
Internal Fragmentation은 발생 가능 (최대 페이지의 크기 - 1)

 

Address Translation Scheme

• Page number (p) : 물리 메모리의 각 페이지의 base 주소가 포함된 페이지 테이블의 인덱스로 사용
• Page offset (d) : base 주소와 결합하여 메모리 유닛으로 전송되는 메모리 주소를 결정
• 논리 주소 공간 : 2의 m승
• 페이지 사이즈 : 2의 n승

Paging Example 1

• 4개의 페이지를 요청하는 프로세스 생성
• OS가 Free Frame Table을 확인
• 물리 메모리의 회색 부분에 할당
• 페이지 테이블에 정보를 적음
• 페이지 크기가 4바이트이면 페이지 오프셋은 2비트가 필요
• 물리 메모리가 32바이트면 프레임 크기는 페이지 크기와 같으므로 8프레임이 존재, 즉 프레임 번호는 8개를 구분해야 하므로 3비트가 필요
• 논리 주소 공간이 16바이트면 4페이지이므로 페이지 번호는 2비트가 필요 / 논리 주소 = 2+2 / 물리 주소 = 3+2
• 논리 주소 0의 물리 주소 => 10100
• 논리 주소 11의 물리 주소 => 00111

Paging Example 2

• 페이지 크기 : 2048 바이트 / 프로세스 사이즈 : 72766 바이트
• 35개의 페이지와 1086바이트가 남으므로 총 36개의 페이지가 필요
• Internal Fragmentation은 2048-1986=962 바이트가 발생
• Worst Case는 1프레임 – 1바이트의 값
• 평균적으로 프레임 크기의 1/2가 발생
• 페이지 크기가 작아지면 페이지 테이블 엔트리가 커짐
• 페이지 테이블 항목을 추적하는데 메모리가 필요하므로 페이지 크기가 작은 게 무조건 좋은 건 아님

Free Frames

• OS가 Frame Table을 유지
• 프로세스가 실행을 요구하면, 몇 개의 페이지가 필요한지 조사하여 할당

Page Table

• 페이지 테이블은 메인 메모리에 유지
• Page Table Base Register (PTBR) - 페이지 테이블의 시작 주소를 가르킴
• Page Table Length Register (PTLR) - 페이지 테이블의 사이즈를 나타냄
• 이 방법은 2번의 메모리 접근이 필요 (1번은 페이지 테이블, 2번째는 데이터/명령어 실행)
• 2번의 메모리 접근 문제를 Translation Look-aside Buffers (TLBs)라는 특수한 고속 검색 하드웨어 캐시로 해결
• TLBs는 기본적으로 작음 (64~1024 엔트리)
• TLB miss가 발생하면 값을 TLB에 로드하여 다음번에 빠르게 접근 가능 (대체 정책도 고려해야 함)

TLB (Translation Look-aside Buffers)

• 소형 하드웨어 캐시로 빠른 연관 메모리(associative memory)로 구성
• 각 항목은 Key와 Value 두 부분으로 구성
• CPU에서 논리 주소를 생성하면, 해당 페이지 번호가 TLB에 전달
• 만약 페이지 번호가 발견되면 해당 프레임을 즉시 알 수 있고, 메모리 접근에 사용
• 만약 없으면(TLB Miss), 페이지 테이블을 접근하기 위해 메모리 참조
• CPU 종류에 따라 하드웨어적으로 이루어지거나 인터럽트를 통해 OS가 처리
• TLB가 가득 차면, 기존 항목 중에서 교체될 항목을 선택
• 몇몇 항목은 TLB에 고정(wired down)하기도 함 (중요 커널 코드)
• 각 항목에 ASID(address-space identifier)를 저장하여 어떤 프로세스에 속한 페이지인지 알려줌
  (프로세스의 정보를 보호하기 위한 목적) (Context Switch 시에 전부 플러쉬하지 않아도 됨)

Effective Access Time (EAT)

• Associative Lookup (연관 검색) = ε 시간 단위 / Hit ratio (히트 비율) = α
• 히트 비율 : 페이지 번호가 연관 레지스터에서 찾아진 비율 / TLB에 원하는 페이지 번호가 있는 비율
• α = 80%, ε = 20ns (TBL 검색), 메모리 접근 시간 = 100ns이면, EAT = 0.80 x 100 + 0.20 x 200 = 120ns
• α = 99%, ε = 20ns (TBL 검색), 메모리 접근 시간 = 100ns이면, EAT = 0.99 x 100 + 0.01 x 200 = 101ns
• TLB에 있으면 메모리 접근 1번의 시간 소요, 없으면 2번의 시간 소요

Memory Protection

• 메모리 보호는 각 프레임에 연결된 보호 비트를 사용 / 읽기 전용 or 읽기/쓰기 접근이 허용되는지 나타냄
• 페이지 테이블의 각 엔트리에는 Valid-invalid 비트가 붙어있음
• Valid는 관련 페이지가 프로세스의 논리 주소에 있으며 legal page임을 나타냄
• Invalid는 페이지가 프로세스의 논리 주소 공간에 없음을 나타냄
• 또는 Page Table Length Register (PTLR) 을 사용
• 어떤 위반 사항(Violation)이 발생하면 커널로의 Trap을 일으킴
• 페이지 단위로 Valid, Invalid 표시 가능, 권한 관리도 가능

Shared Code

• 읽기 전용(재진입 가능)인 코드의 복사본이 프로세스(텍스트 편집기, 컴파일러, 윈도우 시스템 등) 사이에 공유
• 동일한 프로세스 공간을 공유하는 멀티 스레드와 유사
• 읽기-쓰기 페이지 공유가 허용된 Interprocess Communication에 유용

Private Code and Data

• 각 프로세스는 코드와 데이터의 별도 복사본을 유지
• 개인 코드와 데이터의 페이지는 논리 주소 공간 어디에서든 나타날 수 있음

---

Structure of the Page Table

페이징을 위한 메모리 구조가 큰 문제가 발생
32비트 논리 주소 공간일 때, 페이지 크기가 4KB면 (2¹²)

페이지 테이블은 100만개의 항목을 가질 것 (2³²/2¹²)

만약 각 엔트리가 4bytes인 경우, 페이지 테이블은 4MB의 물리적 주소 공간 혹은 메모리가 필요
 -> 막대한 메모리 비용 / 메인 메모리에 연속적으로 할당해야만 하는 문제

 

Hierarchical Paging

• Two-Level Paging Example (Forward-mapped page table)

32비트 머신, 페이지 크기는 1KB(2¹⁰)이면 논리 주소는 22비트의 Page number와 10비트의 Page offset으로 구성
다시 12비트의 Outer Page number와 10비트의 Inner Page number로 구성

• Three-Level Paging Example

64비트 머신, 페이지 크기는 4KB(2¹²)이면 이중으로 충분X
페이지 테이블은 최대 2⁵²개의 엔트리를 가짐
page는 2¹⁰개의 4byte 엔트리로 구성
두 번째 Outer page를 만듦 -> 하나의 물리 메모리 위치에 도달하려면 4번의 메모리 접근 필요

 

Hashed Page Tables

32비트 주소 공간에서 흔함
가상 페이지 넘버가 해싱되어서 페이지 테이블로 들어감
페이지 테이블은 동일한 위치로 해싱되는 요소들의 체인을 포함
각 요소는 가상 페이지 번호 / 매핑된 페이지 프레임의 값
다음 요소를 가리키는 포인터를 포함
체인에서 가상 페이지 번호를 비교하여 일치하는 값을 찾고 해당하는 물리 프레임을 추출
64비트 주소는 Clustered Page Tables 사용
해싱과 비슷, 각 항목은 여러 페이지를 묶어서 참조

 

Inverted Page Tables

각 프로세스가 페이지 테이블을 가지고 모든 가능한 논리 페이지를 추적하는 대신에 모든 물리 페이지를 추적
메모리의 실제 페이지당 하나의 엔트리를 가짐
엔트리는 실제 메모리 위치에 저장된 페이지의 가상 주소와
해당 페이지를 소유한 프로세스에 대한 정보로 구성
각 페이지 테이블을 저장하는데 필요한 메모리를 줄임
페이지 참조가 발생할 때 테이블을 검색하는 시간은 증가
TBL은 접근을 가속화 가능
공유 메모리의 구현 : 가상 주소에서 물리 주소로의 하나의 매핑이 존재

엔트리에 Frame Number 순서대로 정렬을 해놓고 Page Number와 Pid를 매핑해놓음
여러 개의 프로세스가 동시에 접근
CPU가 Logical 주소에서 pid와 page number를 알아내고 page table에서 그 2가지 값을 비교하면서 
Frame Number를 찾음 (만약 없다면 내가 원하는 page는 메모리에 안 올라와 있는 상태)

---

Swapping

프로세스는 일시적으로 메모리에서 스왑되어서 Backing Store로 이동할 수 있음
프로세스의 총 물리 메모리 공간이 물리 메모리를 초과할 수 있음

 

Backing Store

• 모든 사용자의 메모리 이미지의 복사본을 수용할 수 있을 정도로 크고 빠른 디스크
• 이러한 메모리 이미지에 직접 접근을 제공해야 함

Swap time의 대부분의 파트는 전송 시간(Transfer time)

총 전송 시간은 스왑되는 메모리의 양과 직접 비례함

 

Swapped Out된 프로세스는 동일한 물리 주소로 Swap back되어야 하는가? -> 주소 바인딩 방법에 따라 다름

Swapping의 수정 버전은 많은 시스템에서 찾을 수 있음 (UNIX, Linux, Windows 등)

Swapping은 보통 비활성화
일정한 양 이상의 메모리가 할당된 경우에만 시작
메모리 수요가 임계값 아래로 줄어들면 다시 비활성화

 

다음에 CPU로 이동할 프로세스가 메모리에 없는 경우 프로세스를 swap out 하고 대상 프로세스를 swap in 해야 함
-> Context Switch 시간이 매우 길어질 수 있음

 

100MB 프로세스를 50MB/sec의 전송률로 하드디스크로 Swapping하는 경우

• Swap out time : 2000ms
• 동일한 크기의 프로세스를 swap in 하는 시간 : 2000ms
• 총 Context Switch Swapping 구성 시간 : 4000ms = 4초

스왑되는 메모리의 크기를 줄여서 Swapping 시간을 줄일 수 있음
-> 실제로 사용된 메모리의 양을 알아야 함
-> 메모리 사용을 OS에 알리기 위한 시스템 콜 사용 : request_memory( ), release_memory( )

 

Swapping에 대한 제약 사항

• Pending I/O : 대기 중인 I/O의 경우 잘못된 프로세스에 I/O가 발생하므로 Swap out 불가능
• Double Buffering은 오버헤드를 추가함

---

Page 관련 예제

• page size : 4KB (offset으로 계산 -> 12이므로 2의 12승 = 4096바이트)
• inner page table entry size : 4바이트
• inner page table entry 개수 : 2의 10승
• outer page table entry 개수 : 2의 10승
• outer page table entry size : 시스템에 따라 다름