7회차 운영체제 | 세그멘테이션, 페이징, 내부 단편화, 외부 단편화 내용 정리

세그멘테이션, 페이징 (내부단편화 ,외부단편화)

---

가상 메모리 등장 배경

📌 메인 메모리의 용량은 한정적입니다.
 기존에는 프로그램 전부를 메모리에 올려 실행을 하다 보니, 물리 메모리보다 큰 용량의 프로그램을 실행할 수 없었습니다. 이러한 문제를 해결하기 위해서 가상 메모리 개념이 등장합니다.
 또한, 프로세스의 모든 부분은 항상 필요한 것이 아니라서, 현재 실행에 필요한 부분만을 메모리에 올림으로써 해결하는 것입니다.

→ 가상 메모리 기법은 실제 메모리 크기와 프로세스가 올라갈 메모리 위치를 신경 쓰지 않고, 메모리를 이용할 수 있도록 지원하는 기술이다.

가상 메모리

⬛ 가상 메모리 (Virtual Memory)

가상 메모리 적용된 메모리 영

• 가상 메모리는 메모리가 실제 메모리보다 많아 보이게 하는 기술로, 어떤 프로세스가 실행될 때 메모리에 해당 프로세스 전체가 올라가지 않더라도 실행 가능하게 만든 기술이다.
• 가상 메모리는 추상화 기법을 사용하여 물리적 메모리와 프로세스에 대한 가상 메모리 공간을 제공한다.
• 이를 통해 각 프로세스가 ‘자신만의 독립적인 메모리 공간을 가지고 있는 것처럼 동작’한다.
• 또한, 가상 메모리는 메모리 관리의 효율성을 높이고, 여러 프로세스가 동시에 실행할 수 있는 환경을 제공한다.
• 가상 메모리에서 메모리 관리자는 물리 메모리의 부족한 부분을 스왑 영역으로 보충한다.
• 프로세스의 입장에서는 물리 메모리를 신경쓰지 않고 자신이 필요한 만큼 그냥 가상 주소 공간을 사용한다.
• 가상 메모리에서 메모리 관리자가 사용할 수 있는 메모리의 전체 크기는 물리 메모리(실제 메모리)와 스왑 영역을 합한 크기이다.

---

메모리 할당 방식 (연속/ 불연속)

→ 다중 프로그래밍을 위해서는 메모리에 여러 개의 프로세스가 올라와야 한다.

→ 이때 어떤 방식으로 여러 개의 프로세스를 올릴지에 대한 이야기를 의논한다.

   1) 연속 메모리 할당 방식

→ (전제) 하나의 프로세스가 사용하는 공간이 연속적이어야 한다

각각의 프로세스가 통째로 메모리에 물리적으로 연속된 공간에 올라가는 것

(1) 고정 분할 방식 | 관리 편함, 내부 단편화 O

물리적 메모리를 고정된 크기 (파티션)으로 분할하고, 각 분할된 영역에 프로세스 통째로 적재함

→ 내부 단편화 발생: 할당된 메모리 블록 내에서 사용하지 못하는 부분을 의미
  : 메모리 상의 고정된 크기보다 작은 프로세스 배치될 경우(남은 공간) 낭비 공간 발생

(2) 가변 분할 방식 | 관리 힘듬, 외부 단편화 O

물리적 메모리를 (프로세스 크기에 맞춰) 가변 분할 하고, 각 영역에 프로세스 통째로 적재함

프로세스 크기 맞춰서 분할 하니까 내부 단편화 X
→ 외부 단편화 발생 : 메모리 블록들 사이에 사용하지 못하는 공간이 발생하는 것을 의미
  : 예를 들어, 프로세스들 모두 올려둔 상태에서 일부 프로세스 종료되어 나가면, 프로세스 외부에 여러 개의 빈 공간 (홀)들이 산발적으로 생기는데, 이 홀들의 각 공간보다 새 프로세스 크기가 커서 어떤 홀에도 적재를 못하는 상황
 (메모리 낭비)

[외부 단편화 해결 방법 (2)]
(a) 메모리 배치 방식 : 여러 홀 중 어떤 홀에 프로세스 적재시킬지 결정
    최초 적합 : 첫 번째로 발견된 공간에 프로세스 배치
    최적 적합 : 메모리 빈 공간 모두 확인 후, 적당한 크기 중 가장 작은 공간에 프로세스 배치
    최악 적합 : 메모리 빈 공간 모두 확인 후, 가장 큰 공간에 프로세스 배치
(b) 조각 모음 (= 메모리 컴팩션) : 산발된 홀 취합하여 하나의 큰 가용 공간 만들자.
      → 단 이 방식은 메모리 상 위치 이동 시키기 위한 비용 많이 든다.

⇒ 결과적으로 두 방식 모두 단편화를 완벽히 해결 못함

---

   2) 불연속 메모리 할당 방식

→ (전제) 하나의 프로세스가 사용하는 공간이 불연속적이다. (즉, 여러 곳에 분산됨)

가상 메모리를 이용하여 프로세스를 여러 부분으로 나누어 메모리에 할당하는 것

(1) 페이징 (고정 분할) 기법

각 프로세스를 (물리적) 동일한 크기의 ‘페이지’ 단위로 분할하여, 메모리 서로 다른 위치에 할당

장점 : 메모리 관리 비교적 쉬움

단점 : 내부 단편화

(2) 세그멘테이션 (가변 분할) 기법

세그먼트 단위 분할 모습

각 프로세스를 (논리적) 단위인 ‘세그먼트’ 단위로 분할하여, 메모리 서로 다른 위치에 할당

장점 : 공유와 보안 측면

→ 세그멘테이션은 가변 분할 방식이라서 코드 영역, 데이터 영역, 스택 영역, 힙 영역을 세그먼트로 나눠서 관리할 수 있다. 때문에 다른 프로세스와 공유하기도 편하고 각 영역에 대한 메모리 접근 보호를 하기 쉽다

단점: 외부 단편화 (메모리 관리 어려움)

---

   (3) 페이지드 세그멘테이션 | 혼합

혼합된 모

→ 페이징 기법은 메모리 관리는 수월하나 페이지 테이블 크기가 크다는 단점이 있고,

→ 세그멘테이션 기법은 테이블 크기를 작게 유지할 수 있지만, 외부 단편화로 인해 메모리 관리 어렵다는 단점이 있다.

페이징 기법에 세그먼테이션 테이블 추가하여 권한 비트와 같이 중복되는 데이터는 세그먼테이션 테이블로 옮겨 테이블 크기를 줄일 수 있다. 두 테이블을 모두 사용한다.

---

⬛ 메모리 관리자의 역할 | (MMU) Memory Manage Unit

• 메모리 관리자는 메모리를 관리하기 위한 하드웨어

1) 가져오기 (fetch) 정책 : 프로세스가 필요로 하는 데이터를 가져올지 결정하는 정책

2) 배치 (placement) 정책: 가져온 프로세스를 메모리의 어떤 부분에 올릴지 결정하는 정책

3) 재배치(replacement) 정책: 메모리 꽉 찬 경우 메모리 내에 어떤 프로세스를 내보낼지 결정 정책

⬛ MMU의 주소 변환

• MMU는 CPU안에 탑재되어 논리 주소를 물리 주소로 매핑시켜주는 하드웨어 장치이다.

(1) 가상 메모리 도입 (이전) : 연속 할당 방식

→ 연속 할당 방식에서는 한 프로세스 전체가 연속적으로 할당되는 경우이므로 주소 변환 때도 기존 논리주소 + 기준 R 값을 합하면 곧장 물리 주소가 나온다.

메모리 매핑 방식

논리 주소 : CPU 가 생성하는 논리 주소
물리 주소 : (논리주소 + 기준 R 값)으로 얻어진 메모리의 실제 물리 주소
→ 상한(한계) R : 해당 프로세스 접근 가능한 논리 주소 최대 크기 (프로세스 크기)
→ 기준(재배치) R : 현재 수행 중인 프로세스의 물리적 메모리의 시작 주소
⇒ 결과적으로 해당 프로세스는 (기준 R) ≤ 접근 가능 ≤ ( 기준 R + 상한 R )범위 안에서만 접근 가능

(2) 가상 메모리 도입 (이후) : 불연속 할당 방식

→ 불연속 할당 방식에서는 각 논리 주소가 포함된 페이지 번호를 찾고, (페이지 테이블 통해) 프레임 번호를 찾아 실제 물리 주소 상 해당 프레임 + 오프셋 합쳐서 물리주소를 구한다.

논리 주소 : 프로세스가 사용하는 가상 페이지 주소 (페이지 번호, 오프셋으로 구성된 주소)
물리 주소 : 페이지 테이블을 통해 얻은 실제 메모리의 물리주소
→ 페이지 번호로 (페이지 테이블 통해) 실제 메모리 프레임 번호 찾고, 해당 프레임 상에서 오프셋(위치)로 실제 메모리 위치를 찾는다.

---

⬛ 페이징 기법의 주소 변환 과정 설명

VA = <P, D> : 페이지 번호, 오프셋  //가상 주소 표현
PA = <F, D> : 프레임 번호, 오프셋 //물리 주소 표

• 페이지 : 가상 메모리 사용하는 최소 크기 단위
• 프레임 : 물리 메모리 사용하는 최소 크기 단위

페이징 기법 주소 변환 방식

가상 주소 (논리주소) → 물리 주소 변환 과정

• 페이지와 프레임 각 크기를 10byte 로 잡아놨다.

예제 1) 프로세스가 30번지 내용을 읽으려고 한다 .

vA = <3, 0>   ->    PA = <1, 0> 
//가상 주소 30번지는 3번 페이지 0번째에 위치해있다.
//페이지 테이블 거쳐서, 이 주소는 1번 프레임 상 0번째에 위치해있다.(물리주소)

(1) 가상 주소 30번지가 포함된 페이지와 오프셋을 찾는다. (→ 페이지 3의 0번째)

(2) 페이지 테이블 속 페이지 3에 가면, 해당 페이지가 프레임 1에 있다는 것을 알게 된다.

(3) 물리 메모리 상 프레임 1 속 0번째 위치에 접근하면 된다. (이 주소가 가상 주소 30번지의 물리주소)

---

⬛ 세그멘테이션 기법의 주소 변환 과정 설명

VA = <S, D> // 세그먼트 번호, 오프셋
PA = 해당 세그먼트 번호에 해당하는 세그먼트 테이블 상의 시작 주소 + D(오프셋) : 물리주소 

세그먼테이션 주소 변환 방식

가상 주소 (논리주소) → 물리 주소 변환 과정

→ 프로세스 A : 세그먼트 0 에 있다고 치자.

예제 1) 프로세스 A의 32번지에 접근하려고 할 때 주소 변환 과정

(1) 가상 주소를 구한다. VA = <0, 32> 이다.

(2) 세그먼테이션 테이블에서 세그먼트 0의 limit (세그먼트 제한 크기) 보다 오프셋d (32) 가 작은지 확인 (아니면 trap 발생)

(3) 아니라면 세그먼트 0의 시작 주소 (base)인 1400 + 32 (오프셋) 더해서 물리 주소인 1452번지에 접근하여 원하는 데이터 읽거나 씀

📌 세그먼트 테이블의 limit은 페이지 테이블에는 없는데, 그 이유는 세그먼트 크기가 가변적이므로 크기를 명시해야만 해당 세그먼트에 대해서만 접근 가능하기 떄문이다.

---

⬛ 페이지 테이블

각 프로세스는 자신만의 페이지 테이블을 독립적으로 가지고 있다.

MMU를 통해 VPN (Virtual Page Number) → 페이지 테이블 거쳐 → PFN(Pysical Frame Number)로 매핑된다.

페이지 테이블 | Page Table

• 논리주소의 페이지를 물리주소의 프레임으로 매핑시켜줄 정보 담은 테이블

페이지 테이블

1) PTBR | Page Table Base Ragister : 페이지 테이블 베이스 레지스터

• 프로세스 마다 페이지 테이블이 있고,
• CPU 안에 있는 PTBR은 각 프로세스의 페이지 테이블이 적재된 주소를 가리킨다.
• 하지만, 참조할 (페이지 테이블)이 모두 메모리에 있으면 메모리 접근 시간이 2배가 됨

→ 페이지 테이블 참조하기 위해 한 번 (페이지 테이블 접근)

→ 페이지 참조하기 위해 한 번 (프레임 접근)

즉, 완전히 효율적인 방식은 아니다.

PTBR로 주소 참조 모습

2) TLB (Translation Lookaside Buffer) : 페이지 정보 캐시

→ 참조할 (페이지 테이블)이 캐시에 있으면 속도가 더 빠르다.

TLB 활용한 주소 매핑

• TLB : CPU 옆에 있는 (페이지 테이블 일부 가져다 놓은) 캐시 메모리
• 페이지 테이블에 있는 리스트 보관하며, CPU가 페이지 테이블까지 가지 않도록 해서 더욱 속도 향상시킬 수 있는 작은 캐시

1) TLB hit : CPU가 접근하려는 논리 주소가 TLB에 O
→ 메모리 접근 1번
2) TLB fault : CPU가 접근하려는 논리주소가 TLB에 X
→ 메모리 접근 2번
: TLB에 없어서 PTBR이 가리키는 페이지 테이블 주소 찾기 위해 1번
: 페이지 테이블 속 실제 페이지 참조하여 프레임에 접근하기 위해 1번

---

⬛ 페이지 테이블 매핑 방식

1) 직접 매핑 : 페이지 테이블 전체가 물리 메모리의 운영체제 영역에 존재하는 방식

→ 주소 변환 속도 빠르고, 물리 메모리 상 페이지 테이블의 P번째 주소가 시작주소로부터 P번째 위치에 존재함

2) 연관 매핑 : 페이지 테이블 전체를 ‘스왑 영역’에서 관리하는 방식

→ 모든 페이지 테이블을 저장장치의 스왑 영역에 저장하고, 일부만 메모리에 가지고 있다.

3) 집합-연관 매핑 : 모든 페이지 테이블을 스왑 영역에서 관리하고 일부만 물리 메모리로 가져온다는 것은 동일하지만, 페이지 테이블을 일정한 집합으로 자르고 자른 덩어리 단위로 물리 메모리에 가져온다.

4) 역매핑 : 물리 메모리의 ‘프레임’ 번호를 기준으로 테이블을 구성한다.

→ 프로세스 수와 상관없이 테이블 하나만 존재하고, 테이블의 크기가 매우 작다.

---

페이지 폴트 (page fault)

• 가상 메모리 상에는 존재하지만, 실제 메인 메모리 상에는 없는 데이터에 접근한 경우 발생

→ 페이지 폴트 발생 시, 스와핑을 통해 페이지 폴트 일어나지 않은 것처럼 만든다.

스와핑 (swaping)

• 당장 메모리 상에서 사용하지 않는 페이지는 하드 디스크 (스왑 영역)로 옮기고, 하드디스크의 일부분을 마치 메모리처럼 불러와 쓰는 기법

스레싱 (thrashing)

• 원인 : 다중 프로그래밍 정도 높아져서 생김
• 스레싱 : 메모리의 페이지 폴트율이 높은 것 (이는 컴퓨터에 심각한 성능 저하 초래함)
• 스레싱은 메모리에 너무 많은 프로세스가 동시에 올라가게 되면서 반복적으로 페이지 폴트 발생 → 스와핑이 빈번히 일어나 발생하는 것이다.
• 페이지 폴트가 일어나면 (CPU 중단하니까) CPU 이용률이 낮아지는데, OS는 CPU가 한가한 것으로 인식하고 가용성을 더 높이기 위해 더 많은 프로세스를 메모리에 올리게 된다.
• 이런 악순환이 반복되면 ‘스레싱’이 일어난다.

[스레싱 해결 방법] 
(1) 메모리 늘리기

(2) HDD 사용한다면 SDD로 바꾸기

(3) OS가 해결하는 방법 : 작업 세트, PFF
- 작업 세트 (working set) : 프로세스 과거 사용 이력 ‘지역성’ 통해 결정된 페이지 집합 만들어서 미리 메모리에 로드
- PFF (Page Fault Frequency) : 페이지 폴트 빈도를 조절하는 방법. 상한선에 도달하면 프레임 늘리고, 하한선에 도달하면 프레임을 줄임

---

⬛ 페이지 교체 알고리즘

• 페이지 폴트 시, 어떤 페이지를 대상으로 교체하여 (스와핑)할 것인지 결정하는 알고리즘

1) FIFO (First In First Out)

• 가장 먼저 온 페이지를 가장 먼저 교체함
• 성능: 페이지 액세스 패턴이 일정한 경우에는 꽤 효과적이지만, 불규칙한 패턴에서는 성능이 떨어질 수 있음.

2) LRU (Least Recently Used)

• 가장 최근에 사용되지 않은 페이지 교체 (가장 사용한지 오래된) 페이지 교체
• 성능: 일반적으로 좋은 성능을 보이나, 구현이 복잡하고 오버헤드가 크다.

3) LFU (Least Frequently Used)

• 참조 횟수 가장 작은 페이지 교체
• 성능: 일부 시나리오에서는 효과적이지만, 페이지 사용 빈도를 추적하는 오버헤드가 있을 수 있음.

4) MFU (Most Frequently Used)

• 참조 횟수가 가장 많은 페이지 교체
• 성능: 일부 시나리오에서는 빈도를 고려한 적응성이 좋을 수 있으나, 구현이 어려울 수 있

5) OPT (Optimal page replacement)

• 최적 페이지 교체 알고리즘
• 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체

→ 실현 불가능: 미래에 사용하지 않을 페이지를 정확히 예측 불가능하기 때문

→ 보통은 성능 측정할 용도로 사용 (OPT와 비교해서 몇 % 효율 내는지 계산할 때)

• 성능: 가장 이상적인 성능을 제공하지만 현실적으로는 사용되지 않는다.

6) NUR (Not Used Recently)

• 최근 사용되지 않은 페이지 교체 알고리즘
• 참조/변경 비트 (0,0), (0,1), (1,0), (1,1) 순으로 교체
• 성능: 구현이 간단하나 적응성이 제한될 수 있고, LRU를 정확하게 모사하지 못할 수 있음.

---

⬛ 요구 페이징 (demand paging)

요구 페이징은 프로세스의 모든 페이지 정보를 메모리에 저장하지 않고, 실행 중 필요한 시점에서 필요한 페이지만을 메모리에 적재

• 메모리 관리자 (MMU)의 3가지 정책(가져오기, 배치, 재배치) 中 가져오기 정책
• 가져오기 정책 → 사용자가 요구할 때 해당 페이지를 메모리로 가져오는 것

메모리를 효율적으로 사용하기 위한 알고리즘이다. 프로세스가 생성되어도 페이지를 올려놓지 않고있다가, CPU가 필요한 페이지 정보를 찾는 시점에 메모리에 페이지를 업데이트 한다. 이렇게 하면 프로세스 실행 중 필요할 때만 페이지를 메모리에 올리고 사용할 수 있어, 메모리 측면에서 효율적이다.