[운영체제] 가상 메모리

가상메모리

: 보조 메모리를 캐시로 이용하는 것.

 

- 당장 수행할 부분만 메모리에 올려놓는 방식으로, 일부는 물리 메모리에 적재하고 나머지는 디스크 스왑 영역에 적재한다. 이를 요구 페이징 방식이라고 한다.

 

- 다수의 프로그램을 동시에 수행할 때 지역성의 원칙을 적용하여 메모리를 효과적으로 공유한다.

 

- 메인 메모리보다 큰 프로그램을 사용하게 해준다.

 

- 가상 주소를 실제 주소(physical address)로 재배치하는 기능을 제공한다.

=> 가상 메모리 주소는 가상 페이지 번호와 페이지 offset으로 이루어져 있다.

=> 가상 페이지 번호는 physical page의 번호로 변환된다.

=> 페이지 offset은 페이지의 크기를 결정한다.

 

- 이 기능을 주소 바인딩이라고 하며, 바인딩 시점에 따라 3가지로 나눌 수 있다.

=> 컴파일 타임 바인딩: 컴파일 시점 -> 절대코드 생성

=> 로드 타임 바인딩: 프로그램 실행 시작 시점 -> 재배치 가능한 코드

=> 실행 시간 바인딩: 실행중 -> 주소 매핑 테이블, MMU로 주소 매핑

 

- MMU scheme

=> 논리적 주소는 물리메모리의 시작 위치부터 얼마나 떨어져 있는지 알려준다.

=> 한계 레지스터로 프로세스가 자신의 주소 공간을 넘어서 참조하려 하는지 체크한다.

=> 기준 레지스터는 이를 바탕으로 논리적 수로를 물리적 주소로 매핑한다.

 

- write-back 방식을 사용해서 디스크에 데이터를 저장하는 시간을 단축시킨다.

 

페이지(page)

- 가상 메모리블록이다.

 

- 요구하는 페이지를 실제 메모리에서 못찾으면 page fault가 일어난다.

 

페이지 테이블 (page table)

- 가상 주소를 실제 주소로 변환해 주는 테이블이다.

 

- 가상주소의 페이지 번호로 인덱스된다.

 

- 유효-무효 비트로 페이지가 메모리에 존재하는지, 해당 주소 영역을 프로세스가 사용하는지 알 수 있게 한다.

 

페이징 기법

- 물리적 메모리를 프레임(frame)으로 미리 나눈다.

 

- 프로세스의 주소 공간을 동일한 크기의 page로 나눈다.

 

- page와 frame의 크기가 같아 어디든 할당이 가능하다.

 

- 주소 바인딩 과정이 페이지 단위로 이루어진다.

 

- 외부 단편화는 발생하지 않지만, 내부 단편화는 발생할 수 있다.

=> 페이지보다 작은 메모리를 적재하면 남은 부분이 낭비된다.

 

세그멘테이션 기법

- 주소 공간을 의미(기능) 다위의 세그먼트로 나누어 물리적 메모리에 올리는 기법이다.

=> 대표적으로 프로세스 메모리 공간을 예로 들 수 있는데, 기능에 따라 code, data, heap, stack 영역으로 나눈다.

 

- 기능 단위로 공간을 나누기 때문에 세그먼트 크기가 균일하지 않다.

 

- 외부 단편화가 발생할 수 있어 세그먼트에 위치정보와 길이정보를 보관해야 한다.

=> 이 정보를 활용해 세그먼트를 할당할 때 first fit 또는 best fit 방식을 사용한다.

 

페이지드 세그멘테이션 기법

: 세그멘테이션 + 페이징 기법으로 주소 공간을 의미 단위의 세그먼트로 나누고, 각 세그먼트는 페이지의 집합으로 한다.

 

계층적 페이징 기법

: 페이지 테이블에 사용하는 메모리 공간 낭비를 줄인다. 2단계 페이징에서는 외부 페이지 테이블과 내부 페이지 테이블로 계층을 나눈다.

 

외부 페이지 테이블에서는 사용되지 않는 주소공간에 대해서 내부 페이지 테이블 값을 가지지 않는다. (NULL 값을 가진다) 따라서 외부 페이지 테이블에서 1차적으로 물리 메모리에 페이지가 올라가 있는지 확인할 수 있고, 올라가 있을 경우 내부 페이지 테이블을 거쳐 물리 메모리에 엑세스할 수 있다.

 

페이지 교체

- 전역 교체: 모든 페이지 프레임이 교체 대상이다. 

- 지역 교체: 수행중인 프로세스에 할당된 프레임 내에서만 교체 대상이다.

 

<페이지 교체 알고리즘>

- OPT

: 가장 먼 미래에 참조될 페이지를 교체한다.

-> 오프라인 알고리즘으로, 미리 어떤 페이지가 참조될지 다 알고 있어야 한다.

-> 가장 적은 page fault rate를 보장한다. 그래서 다른 알고리즘 성능의 상한선으로 여겨진다.

-> 다른 알고리즘을 테스트할 때 OPT의 page fault rate에 가까워질수록 적합한 알고리즘이다.

 

- FIFO

: 가장 먼저 올라온 페이지를 교체한다.

-> FIFO anomaly: 메모리 공간을 증가시켜도 성능이 더 나빠지는 이상 현상이다.

 

- LRU(least recently used)

: 가장 오래전에 참조가 일어난 페이지를 내쫒는다.

-> 시간 지역성을 활용함.

 

- LFU(least frequently used)

: 참조된 횟수가 가장 적은 페이지부터 교체하낟.

-> Incache-LFU

: 페이지가 물리적 메모리에 올라온 후 참조횟수를 계산한다.

-> Perfect-LFU

: 메모리 상관없이 해당 페이지의 모든 참조횟수를 계산한다.

 

=> 오랜 시간동안의 참조 기록을 반영할 수 있다.

=> 단점: 시간에 따른 페이지 참조 변화는 반영하지 않는다. 

 

- 클럭 알고리즘 (NUR/NRU - Not Recently Used)

: 오랫동안 참조되지 않은 페이지를 교체한다.

1) 교체 페이지를 선정하기 위해 참조 비트를 조사한다. 참조 되었을 때 1로 바꾼다.
2) 참조 비트가 1이면 0으로 바꾸고, 0이면 페이지를 교체한다.
3) 다 조사했으면 처음으로 돌아가 다시 조사한다.

=> LRU와 비슷하지만 참조시간이 오래되었다는 것을 보장할 수 있다.

=> 3번처럼 한번 조사하고 다시 돌아가기 때문에 2차 기회 알고리즘이다.

Thrashing

: 집중적으로 참조되는 페이지 집합을 메모리에 한꺼번에 저장하지 못하면 page fault rate가 상승해 CPU 이용률이 떨어진다.

 

- 가상 메모리가 실제 메모리에 비해 너무 크면 끊임없이 페이지를 교체하게 되는데, 이 과정에서 오버헤드가 발생한다.

CPU 이용률 낮음
-> MPD 높임
-> 너무 높아지면 프로세스가 충분한 프레임을 받지 못함
-> page fault 발생
-> context switch 오버헤드
-> CPU 이용률 낮음

- working-set 알고리즘과 페이지 부재 빈도 알고리즘같이 동적 프레임 할당 알고리즘을 사용해 해결할 수 있다.

Working-set 알고리즘

: 집중적으로 참조하는 페이지의 집합(워킹셋)이 한꺼번에 메모리에 올라갈 수 있게 보장해준다.

=> 워킹셋 크기의 합 > 프레임 수 : MPD 낮춘다.

=> 워킹셋에 프레임을 할당해도 프레임이 남으면 MPD를 높힌다.

 

페이지 부재 빈도 알고리즘

: 페이지 부재율의 하한선, 상한선을 정해서 프레임 수(or MPD)를 조절한다.

- 페이지 부재율이 상한선보다 높으면 페이지 프레임의 할당량을 높이고, 프레임이 부족하면 MPD를 낮춘다.

=> 예를 들어 연봉만큼 직원들이 일을 하는 회사가 있을 때, 부진한 직원의 연봉을 올린다. 연봉을 올릴때 회사 예산을 초과하면 다른 직원을 자른다...

 

- 페이지 부재율이 하한선보다 낮으면 페이지 프레임의 할당량을 감소시키고, 프레임이 남을 경우 MPD를 높힌다.

=> 하는 일에 비해서 연봉이 너무 높으면 연봉을 삭감시킨다.... 남은 예산으로 직원을 더 고용한다....

 

TLB (translation-lookaside buffer)

: 변환 캐시라고 하며, 저장되는 태그 항목에 가상 페이지 번호 일부를 담아 매 참조마다 페이지 테이블까지 안가도 페이지가 메모리상에 있는지 알 수 있다.

 

- 고속의 주소 변환용 하드웨어로, 프로세스가 바뀌면 이전 값을 지운다.

 

- page fault보다 더 빈번하게 참조된다.

 

- 병렬 탐색을 수행한다.

 

Swap space

: 메모리 내의 페이지가 언제 쫓겨날지 알 수 없어 미리 디스크 상에 마련해둔 공간이다.

 

 

 

(참고)

반효경. 운영체제와 정보기술의 원리 2020개정판. 이화여자대학교출판문화원

David A. Patterson, John L. Hennessy (2018). Computer Organization and Design (ARM Edition)