[OS] 페이징과 세그멘테이션, 단편화

0. 개요

내가 실행하고자 하는 프로그램의 용량이 5GB인데, 메모리는 4GB이다. 어떻게 실행할까? 이 때, 사용하는 기술이 바로 가상 메모리이다.

가상메모리

• 실제 메모리 주소가 아닌 가상의 메모리 주소를 주는 방식으로 실행중인 프로세스가 가상의 공간을 참조하여 마치 커다란 물리 메모리를 갖고 있는 것처럼 사용할 수 있도록 하는 것
• 메모리 관리 장치는 가상 주소를 이용해 실제 데이터가 담겨 있는 주소로 변환해 준다.
• 장점
  • 프로그램 용량이 실제 물리 메모리보다 커도 된다.
  • 전체 프로그램이 물리 메모리에 올라와 있지 않아도 된다.
  • 더 많은 프로그램을 동시에 실행할 수 있다.
    • 응답 시간은 유지하면서
    • CPU 이용률과 처리율은 증가

주 기억 장치와 보조 기억 장치

운영 체제는 물리 메모리의 제약을 갖고 있는 메인 메모리(주 기억 장치)를 보조하기 위해 디스크를 보조 기억 장치(Paging Space)로 사용한다.

즉, 메인 메모리 (주 기억 장치)와 디스크의 페이징 스페이스 (보조 기억 장치)를 묶어 하나의 메모리처럼 동작하게 하며, 이를 통해 메인 메모리의 한계를 넘는 메모리 사용을 가능하게 하는 가상 메모리를 구현한다.

Swapping

CPU 할당 시간이 끝난 프로세스의 메모리를 보조 기억 장치로 내보내고 (swap-out) 다른 프로세스의 메모리를 불러오는 (swap-in) 작업을 Swap이라고 한다. 이러한 Swap 작업에는 디스크 전송 시간이 들기 때문에 메모리 공간이 부족할 때 Swapping이 이루어 진다.

---

1. 메모리 관리

다중 프로그래밍 시스템에 여러 프로세스를 수용하기 위해 주 기억 장치 (RAM)을 동적 분할하는 메모리 관리 작업이 필요하다. 즉, 하드 디스크에 있는 프로그램을 어떻게 메인 메모리에 적재할 것인지 판단해야 한다.

• 연속 메모리 관리
  • 프로그램 전체를 하나의 커다란 공간에 연속적으로 할당하는 기법
  • 고정 분할 기법: 주 기억 장치가 고정된 파티션으로 분할 👉 내부 단편화 발생
  • 동적 분할 기법: 파티션들이 동적 생성되며 자신의 크기와 같은 파티션에 적재 👉 외부 단편화 발생
• 불연속 메모리 관리
  • 프로그램의 일부가 서로 다른 주소 공간에 할당될 수 있는 기법
  • 외부 단편화 해소를 위한 페이징과 내부 단편화 해소를 위한 세그멘테이션이 있다.

---

2. 단편화

기억 장치의 빈 공간 또는 자료가 여러 조각으로 나뉘는 현상으로 내부 단편화와 외부 단편화가 있다.

내부 단편화

• 프로세스가 사용하는 메모리 공간에 남는 부분
• 프로세스가 요청한 양보다 더 많은 메모리를 할당할 때 발생

외부 단편화

• 메모리 공간 중 사용하지 못하게 되는 부분
• 메모리 할당 및 해제 작업의 반복으로 작은 메모리가 중간 중간 존재할 수 있다. 이렇게 사용하지 않는 메모리가 존재해서 총 메모리 공간은 충분하지만 실제로 할당할 수 없는 상황이다.
• 압축을 이용하여 프로세스가 사용하는 공간을 한쪽으로 몰 수 있지만, 작업 효율이 좋지는 않다.

---

3. 페이징

• 프로세스를 일정한 크기의 페이지로 분할해서 메모리에 적재하는 방식
• 장점
  • 연속되어 저장될 필요가 없고, 외부 단편화 문제를 해결할 수 있다.
• 단점
  • 내부 단편화 문제가 발생할 수 있다.
    • 페이지 단위를 작게하면 해결할 수 있지만, 페이지 매핑 과정이 복잡해 오히려 비효율적이다.

페이지: 고정 사이즈의 가상 메모리 내 프로세스 조각
프레임: 페이지 크기와 같은 주 기억 장치의 메모리 조각

페이징 테이블

물리 메모리는 고정 크기의 프레임으로, 가상 메모리는 고정 크기의 페이지로 분리되어 있다. 개별 페이지는 순서에 상관 없이 물리 메모리에 있는 프레임에 매핑되어 저장된다.

즉, 모든 프로세스는 하나의 페이징 테이블을 가지고 있으며, 여기에는 메인 메모리에 적재되어 있는 페이지 번호와 해당 페이지가 위치한 메인 메모리의 시작 주소가 있다. 이를 통해 하나의 프로세스를 나눈 가상 메모리 페이지들이 각각 실제 메인 메모리의 어디 프레임에 적재되어 있는지 알아낼 수 있다.

---

4. 세그멘테이션

• 세그멘테이션은 프로세스를 다양한 크기의 논리적 단위인 세그먼트로 분할해서 메모리에 적재하는 방식
• 세그먼트는 의미가 같지 않는 논리적 내용을 기준으로 프로그램을 분할하기 때문에 크기가 같지 않다.
• 장점
  • 내부 단편화 문제 해결할 수 있다.
  • 보호와 공유 기능을 수행할 수 있다. 프로그램의 중요한 부분과 중요하지 않은 부분을 분리하여 저장할 수 있고, 같은 코드 영역은 한 번에 저장할 수 있다.
• 단점
  • 외부 단편화 문제가 생길 수 있다.

세그먼트: 가상 메모리를 서로 크기가 다른 논리적 단위로 분할한 것

세그먼트 테이블

분할 방식을 제외하면, 페이징과 세그멘테이션이 동일하기 때문에 매핑 테이블의 동작 방식도 동일하다. 다만, 논리 주소의 앞 비트들은 페이징 번호가 아니라 세그먼트 번호이다. 세그먼트 번호를 통해 세그먼트의 기준 (세그먼트의 시작 물리 주소)와 한계 (세그먼트의 길이)를 파악할 수 있다.

보호와 공유

• 보호
  • 모든 주소는 페이지 테이블을 경유하므로, 테이블을 이용해서 보호 기능을 수행할 수 있다. 대표적으로 페이지 테이블마다 r(read), w(write), x(execute) 비트를 두어, 해당 비트가 켜져있을 때, 그 수행이 가능하도록 한다.
    
• 공유
  • 공유는 메모리 낭비를 방지하기 위함이다. 같은 프로그램을 쓰는 복수 개의 프로세스가 있다면, 프로세스의 메모리는 code+data+stack 영역으로 나뉘는데 프로그램이 같다면 code 영역은 같을 것이다.
  • 그러므로 하나의 code 영역을 복수 개의 프로세스가 공유하여 메모리 낭비를 줄이는 것이다.

세그멘테이션에서 보호와 공유

세그멘테이션에서의 보호와 공유는 페이징보다 더 효율적이다.

보호에서는 세그멘테이션 역시 r,w,x 비트를 테이블에 추가한다.
하지만 세그멘이션은 논리적으로 나누기 때문에 해당 비트를 설정하기 매우 간단하고 안전하다.
페이징은 code+data+stack 영역이 있을 때, 이를 일정한 크기로 나누므로 두 가지 영역이 섞일 수 있다.
그러면 비트를 설정하기가 매우 까다롭다.

공유도 마찬가지다.
페이징에서는 code 영역을 나눈다해도 다른 영역이 포함될 확률이 매우 높다.
하지만, 세그멘테이션은 정확히 code 영역만을 나눠 더 효율적으로 공유를 수행할 수 있다.

---

5. 어느 것이 좋을까?

세그멘테이션은 페이징과 유사하고 보호와 공유 측면에서는 더 나은 성능을 보여주지만, 현재 대부분은 페이징 기법을 사용한다. 그 이유는 세그먼테이션에는 치명적인 단점이 존재하기 때문이다.

메모리 할당을 처음 시작할 때, 다중 프로그래밍에서의 문제는 크기가 서로 다른 프로세스로 인해 여러 크기의 hole이 발생하고 외부 단편화로 인해 메모리 낭비가 크다는 것이다. 세그멘테이션의 세그먼트 역시 크기가 다양하고 똑같이 다양한 hole이 발생해 같은 문제가 발생한다.

결론적으로 세그멘테이션은 보호와 공유에서 효율적이고, 페이징은 외부 단편화 문제를 해결할 수 있다. 위 두 장점을 살리기 위해 두 가지 방식을 합쳐 세그먼트를 페이징 기법으로 나누는 Paged Segmentation 방식이 나왔다.

하지만, 이 역시 단점이 존재한다. 세그먼트와 페이지가 동시에 존재하기 때문에 주소 변환도 두번해야 한다. 즉, CPU에서 세그먼트 테이블에서 주소 변환을 하고, 그 다음 페이지 테이블에서 또 주소 변환을 해야 한다.

---

6. 요약

• 단편화
  • 내부 단편화
    • 프로세스가 사용하는 메모리 공간에 남는 부분
  • 외부 단편화
    • 메모리 공간 중 사용하지 못하게 되는 부분
• 메모리 관리
  • 연속 메모리 관리
  • 불연속 메모리 관리
    • 페이징
      • 프로세스를 일정한 크기의 페이지로 분할해서 메모리에 적재
      • 외부 단편화 해결, 내부 단편화 발생 가능
    • 세그멘테이션
      • 프로세스를 다양한 크기의 세그먼트로 분할해서 메모리에 적재
      • 내부 단편화 해결, 외부 단편화 발생 가능

---

Reference

https://steady-coding.tistory.com/524
https://github.com/WooVictory/Ready-For-Tech-Interview/blob/master/Operating%20System/Paging_Segmentation.md