📚 가상 메모리
- 이전 포스팅 을 통해, 운영체제가 메모리를 관리하는 전략을 살펴보았다.
✅ 페이징 기법 발전
- 페이징과 스왑을 사용해 실제 메모리보다 더 큰 프로그램을, 외부 단편화 문제 없이 효율적으로 구성하는것을 알아보았다.
- 단 불연속적으로 배치되어있고, 스왑메모리에 일부가 저장되어있는 특성으로 인해, 다음 실행될
페이지의 위치를 빠르게 특정할 수 없는 문제가 발생하였다. 관련 내용 - 즉, 다음에 실행될 페이지가 어떤 프레임에 적재되어있는지 특정할 수 있는 도구가 필요하다.
📌 페이지 테이블
- 이러한 문제를 해결하기 위해 프로세스의 페이지와 실제로 적재된 프레임을 짝지어주는 정보인
페이지 테이블이 존재한다. 페이지 테이블에는 페이지 번호와 실제로 적재된 프레임 번호가 대응되어 있다.- 이
페이지 테이블은, 프로세스 마다 각자의 정보를 가지고 있어, CPU가 서로 다른 프로세스를 실행할 때, 각 프로세스의 페이지 테이블을 참조하여 메모리에 접근한다.
- 즉, 운영체제는
CPU에 우선순위에 따라 일을 시키기 위해, 실제 작업해야 할 정보가 들어있는 저장 위치를 페이지 테이블을 참조해 찾는다.
📌 페이지 테이블 내부 구조
- 페이지 테이블 또한 테이블로, 내부적으로 데이터를 가지고 있다.
- 각각의 행들을
테이블 엔트리라고 부른다. - 운영체제마다 차이는 있지만, 페이지 테이블 엔트리의 속성들은 대표적으로
페이지 번호,프레임 번호,유효 비트,보호 비트,참조 비트,수정 비트등이 있다.
📌 페이지 폴트
- 만약, 운영체제가 메모리에 있지 않은 프로세스 페이지를 실행하려면 어떻게 해야할까?
- 사실 메모리에 없다는 뜻은, 보조 기억 장치등 스왑 영역에 보관되어 있다는 뜻이다.
- 즉, 위 사진에서
프로세스A 의 페이지4등을 실행 할 차례가 되면 어떻게 동작할까? - 이런 경우를
페이지 폴트라고 한다. - 페이지 테이블에는
유효 비트가 있다고 하였는데, 해당 페이지의 유효 비트가 0일 경우, 현재 메모리에 올라가 있지 않다는 뜻이다.
- 위와 같이, 유효 비트가 0인 경우에는 페이지 폴트 발생으로, 페이지 교체 알고리즘등을 사용하여 스왑 영역에서 메모리로 끌어 올리는 작업을 진행해야 한다.
스왑 영역에 있는걸 바로 실행할 수는 없나요? CPU는 오직 “메인 메모리(RAM)”에 올라온 데이터에만 직접 접근할 수 있어. 하드웨어 구조상, 보조기억장치(디스크)에는 직접적으로 실행/접근이 불가능. 스왑 영역(디스크)은 속도가 매우 느리고, CPU가 인식할 수 있는 주소 체계가 아님.
📌 페이지 테이블 - 엔트리 정보
- 페이지 테이블에는 위에 소개한 다양한 정보를 가지고 있다.
보호비트는, 페이지 보호 기능을 위해 존재하는 비트 입니다.r,w,x로 나눠져 있으며, 각각 읽기, 쓰기, 실행 의 순서로 비트로 나눠져 있습니다.- 즉, 보호 비트가 110 으로 되어있다면, 읽기와 쓰기는 허용 되지만 실행은 불가능한 페이지 입니다.
참조 비트는, CPU 가 해당 페이지에 접근한 적이 있는지의 여부를 나타내는 비트 입니다.- 페이지에 적재한 이후, CPU 가 읽거나 쓴 페이지는 참조 비트가 1이 되고, 없다면 0 이 됩니다.
수정 비트는, 해당 페이지에 데이터를 수정한 적이 있는지 확인하는 비트 입니다.Dirty Bit라고도 합니다.- 1인 경우에는 메모리에서 해당 페이지가 수정 되었다는 뜻으로, 메모리의 데이터가 디스크에 있는 데이터와 동일하지 않다는 뜻 입니다.
📌 페이징 기법의 단편화 문제
- 페이징을 통해서
연속 메모리 할당에서 나올 수 있는 외부 단편화를 없앨 수 있었다. - 하지만, 페이징 기법 또한 또다른 단편화 문제가 존재한다.
- 페이징은 프로세스와 메모리 영역을 일정한 같은 단위로 나눠서 관리 하게 된다. (페이지, 프레임)
- 페이지 사이즈 == 프레임 사이즈
- 하지만, 프로세스는 항상 페이지의 배수 만큼 사이즈를 가지고 있지 않는다.
10KB단위로 나눴을때, 프로세스는32KB,64KB일 수도 있고, 이렇게 된다면 어떤 페이지는10KB보다 작은 페이지 사이즈를 가지게 된다.- 만약 이런 페이지를
10KB로 나눠진 프레임에 넣는다면, 남은 공간이 생기게 되고 이는 메모리 비효율이 된다. - 이것을
내부 단편화라고 한다.
✅ 페이지 테이블의 문제점
- 사실 페이지 테이블 또한 정보를 가지고 있는 데이터로, 결국 어딘가에 저장 되어야 합니다.
- 즉 CPU 가 페이지에 접근해 작업을 하려면,
페이지 테이블이 어디에 있는지 알아야 되는 것 입니다.
📌 PTBR
- CPU 내부에는 아주 소수의 초고속 저장공간인 레지스터가 있는데, 이곳에 특정 프로세스의 페이지 테이블이 적재된 메모리 상의 위치를 가르키도록 저장되어 있다.
- 이를
PTBR(Page Table Base Register)이라고 한다. - 즉, CPU는,
PTBR을 통해페이지 테이블에 접근,페이지 테이블을 통해 실제 프로세스가 적재된프레임에 접근하여 실행 하는 구조를 가지게 된다. - 결국 하나의 프로세스 페이지에 접근하기 위해서 많은 접근을 해야 하는 것이다.
📌 TLB
- 위의
PTBR을 사용한 페이지 찾기의 문제를 캐시를 통해 일부 해소한 것이TLB(Translation Look-aside Buffer)이다. - TLB는 페이지 테이블의 캐시 메모리로, CPU가 접근 하려는 논리 주소의 페이지 번호가
TLB에 있는 경우,PTBR->페이지테이블의 흐름으로 접근하지 않고 바로 프레임으로 접근하여 실행한다. - 이를
TLB 히트라고 한다. TLB 히트된다면, 이전과 다르게 한번만 메모리에 접근해도 되서, 빠르게 처리 된다.- 하지만, 원하는 페이지 정보가 TLB에 없다면, 결국
PTBR을 통해 two-depth 로 접근하여 조회해야 하는데, 이를TLB 미스라고 한다. - 그런데, 또다시 의문이 발생한다.
- 페이지 테이블은 프로세스의 사이즈에 따라 선형적으로 증가하게 된다.
- 모든 내용이 페이지 테이블에 메모리에 있는 것은 메모리 낭비이다.
📌 계층적 페이징
- 위의 문제를 해결하기 위해,
계층적 페이징구조를 사용한다. 다단계 페이지 테이블기법 이라고도 부른다.- 계층적 페이징은, 페이지 테이블을 여러 개의 페이지로 자르고, CPU 와 가까이 위치한 바깥 쪽에 테이블을 하나 더 두어 잘린 페이지 테이블의 페이지들을 가리키게 한다.
- 이렇게 페이지 테이블을 계층적으로 구성해두면, 모든 페이지 테이블을 항상 메모리에 유지할 필요가 없어진다. (메모리 절약)
- 이 Outer 페이지 테이블만 메모리에 유지하면, 잘린 페이지 테이블의 일부가 보조 기억 장치에 있더라도 Outer 페이지 테이블을 통해 언제든 접근할 수 있기 때문이다.
페이지 테이블의 계층은 3개, 4개, 그 이상으로도 구성될 수 있다.
✅ 페이징 주소 체계
📌 논리 주소(Logical Address)의 구성
- 페이징 시스템에서 **프로세스가 사용하는 주소(=가상주소, 논리주소)**는 두 부분으로 나누어진다.
- 페이지 번호(Page Number, p)
- 논리 주소에서 “몇 번째 페이지인지”를 나타냄
- 페이지 테이블에서 해당 페이지의 정보를 찾을 때 사용
- 변위(오프셋, Offset, d)
- 해당 페이지 안에서의 **상대적 위치(몇 번째 바이트인지)**를 나타냄
예시 만약 페이지 크기가 4KB(=2¹²B)라면 하위 12비트 → 오프셋 나머지 상위 비트 → 페이지 번호
주소 비트 의미 상위 N비트 페이지 번호 p 하위 M비트 오프셋 d
- 다음과 같은 예시에서, 5번 페이지, 변위 2 즉, 논리 주소 <5, 2> 에 접근한다면 실제로 CPU는 1번 프레임의 물리 주소 공간 8번지부터 접근하게 된다.
✅ 페이지 교체 알고리즘
- 위에서 짧게 언급되었는데, 모든 페이지들은 메모리에 적재 되어 있지 않다고 하였다.
- 메모리에 프로세스를 적재할 때, 처음부터 모든 페이지를 적재하지 않고, 메모리에 필요한 페이지만을 적재하는 기법을
요구 페이징이라고 한다.
📌 요구 페이징
- 요구 페이징의 기본적인 양상은 다음과 같다.
- CPU가 특정 페이지에 접근하는 명령어를 실행
- 해당 페이지가 현재 메모리에 있을 경우, CPU는 페이지가 적재된 프레임에 접근 한다. (페이지 테이블의 유효비트가 1인 경우)
- 해당 페이지가 현재 메모리에 없을 경우,
페이지 폴트가 발생- 페이지 폴트가 발생하면, 페이지 폴트 처리 루틴을 통해 해당 페이지를 메모리로 적재하고, 유효 비트는 1로 다시 설정한다.
- 다시 1의 과정을 수행한다
- 참고로, 아무런 페이지도 메모리에 적재하지 않은 채 무작정 프로세스를 실행할 수도 있는데 이를
순수 요구 페이징이라고 한다. 순수 요구 페이징의 경우에는 프로세스의 첫 명령어를 실행하는 순간부터 페이지 폴트가 발생하게 되고, 실행에 필요한 페이지가 어느 정도 적재된 이후부터는 페이지 폴트의 발생 빈도가 떨어지게 된다.
📌 페이지 교체 알고리즘
- 요구 페이징을 통해 페이지들을 메모리에 점차 적재 하다보면 언젠가는 메모리가 가득 찰 것이다.
- 적재된 페이지 중, 보조기억장치로 스압 아웃 할때, 내보낼 페이지를 선택하는 방법을
페이지 교체 알고리즘이라고 한다. - 페이지 교체 알고리즘에는 다양한 종류가 있지만 대표적으로 3개가 존재 한다.
📌 페이지 교체 알고리즘 - FIFO
- 정의
- 가장 먼저 메모리에 올라온 페이지를 가장 먼저 내보내는(교체하는) 방식.
- 동작 방식
- 큐(Queue) 자료구조 사용.
- 새로운 페이지를 적재해야 할 때, 가장 먼저 들어온 페이지를 무조건 교체.
- 특징:
- 구현이 가장 단순함.
- 페이지 참조의 시간적 특성을 전혀 고려하지 않음.
- 장점:
- 구현이 쉽고 오버헤드가 적음.
- 단점:
- “Belady’s anomaly(벨라디의 모순)”가 발생할 수 있음 (프레임 개수를 늘려도 오히려 페이지 폴트가 증가하는 현상)
- 실제 사용 패턴을 고려하지 않아 성능이 떨어질 수 있음.
📌 페이지 교체 알고리즘 - 최적 페이지 교체 알고리즘 (OPT)
- 정의
- 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 방식. (이론적으로 최적)
- 동작 방식
- 앞으로의 참조 순서를 미리 알고 있다고 가정.
- 새 페이지가 필요할 때, 앞으로 가장 오랫동안 참조되지 않을 페이지를 교체.
- 특징
- 현실적으로 구현은 불가능하지만, 모든 교체 알고리즘 중 가장 적은 페이지 폴트를 보장.
- 장점
- 이론적으로 최적의 성능.
- 다른 알고리즘의 성능 비교 기준으로 사용됨.
- 단점
- 미래의 참조 순서를 알아야 하므로 실제 시스템에선 구현 불가.
📌 페이지 교체 알고리즘 - LRU
- 정의
- 가장 오랫동안 사용되지 않은 페이지를 교체하는 방식.
- 동작 방식
- 각 페이지의 마지막 참조 시점을 기록.
- 새 페이지 필요 시, 가장 오래전에 사용된 페이지부터 교체.
- 특징
- 시간적 지역성(최근에 사용된 데이터가 곧 다시 사용될 가능성)을 반영.
- 실제로 많이 사용되는 알고리즘.
- 장점
- 프로그램의 실제 접근 패턴과 잘 맞아 좋은 성능을 보임.
- OPT(최적)와 비슷한 성능 가능.
- 단점
- 참조 시점 기록/관리 비용이 큼.
- 완전한 LRU 구현은 어려워 근사치를 사용하거나 하드웨어 지원이 필요함.