05. 가상 메모리의 이해

#실제 각 프로세스마다 충분한 메모리를 할당하기에는 메모리 크기가 한계가 있음 

 

리눅스는 하나의 프로세스가 4GB 인데 통상적으로 우리의 PC의 메모리는 8GB나 16GB 이기 때문에

하나, 두 개의 프로세스만 사용해도 많은 부분을 차지하게 된다.
게다가 폰노이만 구조에 의해 코드는 무조건 메모리에 반드시 있어야한다는 사실
그렇다면 여러 프로세스를 실행하기 위해서는 어떤 메모리 구조를 가져야할까?? 

이 질문에 대한 답이 바로 가상 메모리 이다.

 

 

 

#가상 메모리(virtual memory system) 개념
프로세스 내에서 실제 어느 시점에 CPU가 쓰는 공간은 제한적이다. 
한 번에 4GB가 사용되지 않는다.

한 번에 4GB를 읽지 않는다.
특정 시간 동안 사용하는 특정 메모리는 제한적이다.

실제 사용하는 메모리는 작다는 점에 착안해서 고안됨 
특정 프로세스 공간에서 지금 당장 CPU가 사용하는 공간만 메모리에 넣어주겠다. 

 

메모리가 실제 메모리보다 많아 보이게 하는 기술

 

 

 

#가상 메모리가 필요한 이유 

가상 메모리는 여러 프로세스 동시 실행 시스템에서 사용이 된다. 
메모리 용량 부족에 대한 문제나

프로세스 메모리 영역 간 공간 분리로 메모리 영역 간 침범에 대한 문제를 해결하기 위해서 필요하다.

그렇기 때문에 프로세스 이슈가 전체 시스템에 영향을 주지 않을 수 있음

하나의 프로세스만 실행 가능한 시스템에서는 가상 메모리를 쓸 이유가 거의 없다. (배치 처리 시스템 등)

1. 프로그램을 메모리로 로드
2. 프로세스 실행
3. 프로세스 종료 (메모리 해제)

 

#가상 메모리 기본 아이디어
프로세스는 가상 주소를 사용하고, 실제 해당 주소에서 데이터를 읽고 쓸때만 물리 주소로 바꿔주면 된다.
그 메커니즘은 가상 시스템 메모리 안에 들어가 있음.

Virtual address (가상 주소) 
프로세스가 참조하는 주소, 0~4GB

Physical address (물리 주소) 
실제 메모리 주소, 0~4GB 중의 일부분만 메모리에 올라감

 

#MMU (Memory Management Unit)  
CPU에 코드 실행 시, 가상 주소 메모리 접근이 필요할 때,  
해당 주소를 물리 주소값으로 변환해주는 시간을 줄이기 위해 사용하는 하드웨어 장치 

 

CPU는 가상 메모리를 다루고, 

실제 해당 주소 접근 시 MMU 하드웨어 장치를 통해 물리 메모리에 접근을 해서 해당 데이터를 다시 CPU에 전달함
하드웨어 장치를 이용해야 주소 변환이 빠르게 때문에 별도 장치인 MMU를 둠

 

가상 메모리와 MMU의 관계

 

---

#페이징 시스템
가상 메모리 시스템에서 가장 많이 쓰이는 시스템
특정 시간에 프로세스에서 얼마만큼의 양을 메모리에 올려둘 것인가?? 에 대한 문제를 해결하기 위함

크기가 동일한 페이지로 가상 주소 공간과 이에 매칭하는 물리 주소 공간을 관리
하드웨어 지원이 필요 
ex. Intel x86시스템(32bit)에서는 페이지 사이즈 단위를 4KB, 2MB, 1GB 지원
ex. 리눅스에서는 4KB로 Paging
페이지 번호를 기반으로 가상 주소/물리 주소 매핑 정보를 기록/사용

 

#페이징 동작 원리
프로세스(4GB)의 PCB에 Page table 구조체를 가리키는 주소가 들어 있음
그리고 Page Table에는 가상 주소와 물리 주소간 매핑 정보가 있음

CPU가 가상 주소에 접근을 하려고 하면 해당 주소를 보고 Page 번호를 본 다음 Page Table에
가상 주소에 매칭되는 물리 주소를 알아 낸 다음 해당 실제 물리 메모리내의 정보를 얻고 CPU에서 처리한다.

 

 

#페이징 시스템 구조
Page 또는 Page frame

고정된 크기의 block(4KB)

9KB의 데이터의 경우 1KB가 남더라도 물리 메모리에 넣을 때는 1KB와 공란인 3KB 까지 묶어서 처리한다.

가상 주소 V = (p, d)
p : 가상 메모리 페이지 번호
d : p안에서 참조하는 위치, 변위(오프셋)

* 해당 페이지번호의 base 주소에서 4KB 내의 원하는 코드가 있는 위치를 찾기 위해 d가 필요
* 페이지 크기가 4KB 일 때 가상 주소의 0~11 bit가 변위 d를 나타내고, 12 bit 이상이 페이지 번호가 될 수 있음

 

#프로세스가 리눅스에서 4GB를 사용하는 이유

32 bit 시스템에서 2의 32승이 4GB

즉 32 bit로 모두 표현 가능해서

 

 

#페이지 Table  
물리 주소에 있는 페이지 번호와 해당 페이지의 첫 물리 주소 정보를 매핑한 표
p : 페이지 번호
d : 페이지 처음부터 얼마 떨어진 위치인지

해당 프로세스에서 특정 가상 주소를 엑세스를 하려면
해당 프로세스의 PCB에 Page table의 가상 주소(첫 주소=base주소)를 가지고 와서
페이지 번호만 알면 page table에서 해당 page 까지 넘어간다음 해당 page에 해당되는 물리 주소가 있는 것
그 물리 주소와 d 를 알면 메모리의 데이터 값을 알아 낼 수 있음

page 번호가 있으면 이 page가 매핑된 첫 물리 주소를 알아내고(p`)
p` + d가 실제 물리 주소가 됨

 

 

#페이징 시스템과 MMU 
CPU가 가상 주소 접근 시 
MMU가 하드웨어 장치를 통해 물리 메모리에 접근을 할 때 가상 주소를 물리 메모리로 바꿔줌

프로세스 생성 시, 페이지 테이블 정보 생성
PCB 등에서 해당 페이지 테이블 접근 가능하고, 관련 정보는 물리 메모리에 있음
프로세스 구동 시, 해당 페이지 테이블 Base 주소가 별도 레지스터에 저장(CR3)
CPU가 해당 프로세스를 실행 하기 위해 가장 주소 접근 시, 
MMU가 페이지 테이블 base 주소를 접근해서, 물리 주소를 가져와서 CPU에 넘겨준다.



#다중 단계 페이징 시스템
프로세스 내 4GB의 공간을 4KB 의 단위로 페이지를 만들면 페이지 테이블도 많은 영역을 차지
0~3GB의 대부분의 영역은 거의 쓰이지 않는데 그것들 때문에 페이지 테이블 공간, 메모리 낭비를 할 수 있음

페이징 정보를 단계를 나누어 생성한다.
공간을 나눌 수 있는 페이지 디렉토리를 만들어서 필요없는 페이지에 대해 페이지 테이블을
생성하지 않게 하여 공간 절약 가능

32 bit 시스템에서 4KB 페이지를 위한 페이징 시스템은
하위 12 bit는 오프셋(변위)
상위 10 bit는 페이지 디렉토리
CRP3 레지스터는 페이지 디렉토리의 시작 주소가 담김
상위 10 bit는 페이지 테이블
페이지 디렉토리에서 사용하는 것들만 모아놓아서 테이블을 만들게 되면 효율적이다!

상위 20 bit 가 페이징 번호 이므로, 2의 20승 (1048576)개의 페이지 정보가 필요함

 

#MMU와 TLB
CPU가 가상 메모리를 요청하면 MMU에서 CR3 레지스터(Base address) 값을 가지고
페이지 테이블에 들어가서 물리 주소를 가져 온 다음 그 물리주소에 MMU 가 접근해서
해당 DATA를 CPU에 전달하게 됨.

하지만 메인 메모리에 왔다갔다 하는 시간이 오래 걸림!
그래서 별도의 캐시 보조 하드웨어를 넣게되었는데 그것이 - TLB 페이지 정보 캐쉬

 

가장 최근에 가상 주소와 물리 주소로 변환된 주소를 저장해두고
다시 이전에 요청했던 가상 주소를 다시 요청하게 되면 Page table을 가는게 아니라 MMU가
TLB에 해당 물리주소가 있는지 찾아보고 바로 CPU에 전달하게 됨

 

MMU와 TLB

 

 

 

 

 

#페이징 시스템의 이점

공유 메모리
프로세스 간 동일한 물리 주소를 가리킬 수 있음(공간 절약, 메모리 할당 시간 절약)

몇 가지 기술이 가능
1. 프로세스 내의 3~4GB 공간인 커널 영역은 이 공간에 프로세스 각각마다 갖는 것처럼 보이지만 그렇지 않다.
해당되는 페이지 테이블은 동일한 물리 메모리 공간을 가리키면 되기 때문에 아깝지 않게됨

2. 부모/자식 Process

3. 물리 주소 데이터 변경 시
물리 주소에 데이터 수정할 때, 물리 주소를 복사할 수 있음 (copy-on-write)
프로세스 생성 시간을 줄일 수 있다.
커널, 공유 메모리 등 공유하는 데이터는 별도 공간이 필요없어서 공간 절약 가능하다.
단순히 page table 의 해당 page 물리 주소만 바꾸면



#요구 페이징(Demand paging) 기법
프로세스 모든 데이터를 메모리로 적재하지 않고, 실행 중 필요한 시점에서만 메모리로 저장함

선행 페이징의 반대 개념

 

 

#선행 페이징(prepaging) 기법
미리 프로세스 관련 모든 데이터를 메모리에 올려놓고 실행하는 개념
더 이상 필요하지 않은 페이지 프레임은 다시 저장매체에 저장 (페이지 교체 알고리즘 필요)

 

#페이지 폴트(page fault) 인터럽트
어떤 페이지가 실제 물리 메모리에 없을 때 일어나는 인터럽트
운영체제가 page fault가 일어나면, 해당 페이지를 물리 메모리에 올림

 

 

#페이지 폴트 인터럽트를 포함한 전체적인 구조
CPU가 가상 주소를 요청하면 
MMU는 우선 TLB에 가서 해당 가상 주소에 대한 물리 주소가 있는지 확인을 하고 
가상 주소에 대한 물리 주소가 있다면 바로 Memory에 갔다가 CPU에 처리하게 됩니다. 
가상 주소에 대한 물리 주소가 없다면 CR3 레지스터에 간 다음 Memory의 Page table로 가서 valid/invalid 확인합니다. 
valid - 해당 물리 주소가 있다면 CPU에 데이터 전달하게 되고
invalid - 해당 물리 주소가 없다면 페이지 폴트 인터럽트를 운영 체제에 전달합니다.
해당 인터럽트 번호에 대한 운영 체제 함수 호출을 한 다음 운영 체제가
해당 Page를 저장 매체에서 가져와서 해당 데이터를 Memory에 올려주고
그 다음 해당 페이지와 관련된 Page table을 업데이트 하여 CPU에게 다시 실행해라고 합니다.
그리고 다시 처음부터 protocol 진행하게 됩니다.

 

 

 

MMU, Memory, OS의 관계

 

---

#페이지 폴트가 자주 일어나면??
구조가 복잡하기 때문에 시간이 오래 걸린다. 
그렇기 때문에 실행되기 전에, 해당 페이지를 물리 메모리에 올려놔야 하는 필요성이 있음 

 

 

#페이지 폴트가 안 일어나게 하려면? 
향후 실행/참조될 코드/데이터를 미리 물리 메모리에 올리면 됨 
앞으로 있을 일을 예측해야 함 - 신의 영역

 

이것을 위한 여러 알고리즘이 존재함 

 

 

 

#페이지 교체 정책
운영 체제가 특정 페이지를 물리 메모리에 올리려 하는데, 물리 메모리가 다 차있다면??
기존 페이지 중 하나를 물리 메모리에서 저장 매체로 내리고(저장)
새로운 페이즈를 해당 물리 메모리 공간에 올린다.

어떤 페이지를 물리 메모리에서, 저장 매체로 내릴 것인가?
Page Replacement Algorithm 의 개념 등장

 

 

 

 

 

Page Replacement Algorithm 

#FIFO
가장 간단한 알고리즘으로, 메모리에 올라온 지 가장 오래된 페이지, 가장 먼저 들어온 페이지를 교체한다.
이 알고리즘을 수행하기 위해서 각 페이지가 올라온 시간을 페이지에 기록하거나,
페이지가 올라온 순서를 큐에 저장하는 방식등을 사용할 수 있다.

이해가 쉽고, 구현이 간단하지만
하지만 활발하게 사용 중인 페이지를 계속해서 교체한다면

페이지 부재율이 높아지고

실행속도가 떨어질 위험이 있다.



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

최적 알고리즘을 수행하기 전 선행되어야 할 전제조건이 존재
'프로세스가 앞으로 사용할 페이지를 미리 알아야 한다'
이 전제 조건이 실제 활용에서는 알 방법이 없기 떄문에 최적 알고리즘은 일반 
운영 체제에서 구현이 불가능한 알고리즘이다.

때문에 실제 구현 목적보다는 다른 알고리즘과 비교 연구 목적을 위해 사용된다.

최적 교체 알고리즘은 가장 오랫동안 사용되지 않을 페이지를 알고 교체하기 때문에
모든 페이지 교체 알고리즘을 통들어 가장 페이지 교체 수가 적다.



#LRU(least-recently-used)
가장 오래 사용되지 않은 페이지를 교체하는 알고리즘

최적 알고리즘은 실제 구현이 불가능하므로, 최적 알고리즘의 방식과 비슷한 효과를 낼 수 있는 방법을
사용한 것이 LRU 알고리즘

최적 알고리즘은 페이지가 사용될 시간을 미리 알고 있다.
미리 아는 것이 불가능하다면, 과거의 데이터를 바탕으로 페이지가 사용될 시간을 예측하여 교체하는 것은
불가능하다. 예측 방법으로 가장 오랜 기간 사용되지 않는 페이지를 교체하는 방식을 사용하는 것이다.

최적 알고리즘보다 페이지 교체 횟수가 높지만, FIFO 알고리즘 보다 효율적이다.
LRU는 많은 운영체제가 채택하는 알고리즘




계수 기반(counting-based) 페이지 교체 : 페이지 참조 시마다 각 페이지가 현재까지 참조된 횟수를 
카운팅하는 방법이다. 이 방법을 이용해 두 가지의 알고리즘을 만들 수 있다.

#LFU(least-frequently-used)
참조 횟수가 가장 작은 페이지를 교체하는 알고리즘
만약 교체 대상인 페이지가 여러 개 일 경우, LRU 알고리즘을 따라 가장 오래 사용되지 않은 페이지로 교체한다.

초기에 한 페이지를 집중적으로 참조하다가 이후 다시 참조하지 않는 경우 문제가 될 수 있다.
앞으로 사용하지 않아도 초기에 사용된 참조횟수가 높아 메모리에 계속 남아있기 때문이다.

 

#MFU(most-frequently-used)
LFU와 반대로 참조 횟수가 가장 많은 페이지를 교체하는 알고리즘
참조 횟수가 적은 페이지가 최근에 사용된 것이기 떄문에 앞으로 사용될 가능성이 높다는 판단이다

LFU,MFU 는 실제 사용에 잘 쓰이지 않는다.
구현에 상당한 비용이 들고, LRU 만큼 최적 페이지 교체 정책을 제대로 유사하게 구현해내지 못하기 떄문이다.



#페이지 스왑 알고리즘(NUR Not used recently)
LRU와 마찬가지로 최근에 사용하지 않은 페이지부터 교체하는 기법
각 페이지마다 참조 비트(R), 수정 비트(M)을 둠(R,M)
(0,0),(0,1),(1,0),(1,1)순으로 페이지 교체

 

 

#Thrashing 스레싱
반복적으로 페이지 폴트가 발생해서, 과도하게 페이지 교체 작업이 일어나,
실제로는 아무일도 하지 못하는 상황





#세그멘테이션 기법(Segmentation) - 페이징 시스템과 비교

페이징 기법에서는 가상 메모리를 같은 크기(4KB)의 블록으로 분할
세그먼테이션은 부위별로 다른 크기로 자르는 것
가상 메모리 메커니즘 하나
세그멘테이션은 크기가 다른 segment 단위로 물리 메모리에 로딩

가상 메모리를 서로 크기가 다른 단위인 세그먼트로 분할
ex. x86 리얼모드(인텔의 CPU
CS(Code Segment),DS,SS,ES 로 세그먼트를 나누어, 메모리 접근

 

#세그먼트 가상 주소
v = (s,d) s는 세그먼트 번호, d는 블록 내 세그먼트의 변위

 

#세그멘테이션 vs 페이징

페이지 기법 - 내부 단편화 문제 발생
페이지 블록만큼 데이터가 딱 맞게 채워져 있지 않을 때 공간 낭비가 있을 수 있음

세그멘테이션 기법 - 외부 단편화 문제 발생
물리 메모리가 원하는 연속된 크기의 메모리를 제공해주지 못하는 경우

세그멘테이션/페이징 모두 하드웨어 지원 필요
다양한 컴퓨터 시스템에 이식성을 중요시하는 리눅스는 페이징 기법을 기반으로 구현

 

세그먼테이션 VS 페이징 기법

 

 

 

#가상 메모리 동작 이해 총정리
코드 → 컴파일 → 실행 파일 1KB → 쉘 → 실행 → 프로세스 → 가상 메모리 4GB (실행 파일이 1KB 밖에
안되더라도 가상 메모리는 4GB가 잡힘)
 

#lazy allocation
최대한 할당을 지연해서 시간을 아끼고자 하는 것
실행 파일이 가상 메모리 화되어서 프로세스가 만들어질 때 프로세스가 실행이 되었을 때
해당 데이터가 필요한 시점이 되기 전까지는 어느 데이터도 파일에서 물리 메모리로 넣지 않는 것