08.가상 메모리
가상메모리 개요
가상메모리란?
컴퓨터마다 실제 메모리 크기가 다르다. 운영체제나 프로세스가 4GB에서 동작하도록 만들어졌다면, 더 작은 메모리에서는 실행을 못할 것이다. 이런 문제를 해결하는 것이 가상메모리이다.
프로세스는 운영체제 영역이 얼마나 되는지, 물리메모리의 크기가 어떤지 고려하지 않아도 된다.
물리 메모리에 직접 접근하지 않고, 메모리 관리자를 통해 메모리에 접근하기 때문이다.
가상 메모리의 크기는 이론적으로는 무한대이지만, 실제 크기는 물리 메모리의 크기와 CPU의 비트 수로 결정된다. (2^32 → 4GB)
가상메모리가 부족한 메모리를 어떻게 해결할까?
가상 메모리 시스템에서 운영체제 영역을 제외하고, 메모리의 공간을 일정하게 나누어서 제공한다.
가변 분할 방식, 고정 분할 방식을 결합한 세그멘테이션 페이지 혼용기법 사용
가상메모리 시스템에서의 가상주소는 메모리나 스왑영역 중 한 곳에 위치한다.
메모리 관리자는 물리메모리와 스왑 영역을 합쳐 가상주소를 물리주소로 변환한다. (동적 주소 변환, DAT)
메모리 관리자는 가상주소와 물리주소를 일대일 매핑주소로 관리한다.
메모리 배치 정책(세그멘테이션과 페이징)
세그멘테이션 기법 (가변 분할 방식)
세그멘테이션은 함수, 데이터, 라이브러리, 모듈 등으로 프로그램을 구성하며, 각 세그먼트들은 서로 인접할 필요가 없다. 그러나 프로세스의 입장에서는 코드, 데이터, 힙, 스택 영역을 서로 인접한 것처럼 바라본다.
사용자, 프로세스, CPU가 사용하는 주소 = 논리주소
메모리 관리자(MMU)가 실제 물리주소로 변환해준다.
메모리 관리자가 물리주소로 변환하는 방법
세그멘테이션 테이블을 통해 관리한다.
Base address, Bound address를 기반으로 계싼한다.
구체적 단계
CPU에서 논리주소를 전달하면, 메모리 관리자는 해당 주소가 몇 번 세그먼트인지 확인한다.
메모리 관리자 내 세그먼트 테이블 베이스 레지스터를 이용해 물리 메모리 내에 있는 세그멘테이션 테이블을 찾는다.
세그먼트 번호를 기반으로 Base adress, Bound adress를 찾는다. (Bound adress = 세그먼트의 크기)
요청받은 논리 주소와 Bound adress의 크기를 비교했을 때, Bound adress가 더 크다면, Base adress + 논리주소를 통해 물리주소를 계산하고, Bound adress가 더 작다면 메모리를 침범했다고 생각하여 에러를 발생시킨다.
장점
메모리를 가변적으로 분할할 수 있다.
코드, 데이터, 스택, 힙 영역을 모듈로 처리할 수 있어서 공유와 각 영역에 대한 메모리 접근 보호가 편리한다.
단점
외부 단편화가 발생한다.
참고사항
컨텍스트 스위칭이 일어날 때마다 세그먼트 테이블 베이스 레지스터는 새로 바뀐 프로세스것으로 업데이트해주어야한다. (이런 과정도 포함되어있어서 컨텍스트 스위칭이 무거운 것이다)
페이징 (고정 분할 방식)
💡 세그멘테이션은 외부 단편화 문제가 있어서 이를 해결하기 위해 탄생한 방법이다. (조각 모음을 통해 해결은 할 수 있지만, 오버헤드가 너무 크다)
메모리를 정해진 크기의 페이지로 나눈다.
모든 페이지의 크기가 같아서 관리가 쉽다.
일정한 크기로 나누기 때문에 외부 단편화 현상이 발생하지 않는다. (내부 단편화 발생)
페이징에서 논리 주소 공간(사용자, 프로세스 관점)은 일정한 크기로 균일하게 나뉘며, 페이지라고 부른다.
페이징에서 물리 주소 공간(실제 메모리에 관점)은 페이지와 동일한 크기로 나뉘며, 프레임이라고 부른다.
페이징에서 주소변환
메모리 관리자가 페이지 테이블을 가지고 있다.
CPU에서 논리 주소를 전달하면, 몇 번 페이지인지, 오프셋은 몇인지 구한다.
메모리 관리자 내에 페이지 테이블 베이스 레지스터를 이용한다.
물리 메모리에 있는 페이지 테이블을 찾는다.
페이지 넘버와 오프셋을 계산하여 물리 주소로 변환한다.
Page numer(인덱스) = 논리주소 / 페이지 크기
offset = 논리주소 % 페이지 크기
page Table[index] = Frame 번호 로 저장되어있다.
만약 프레임에 invalid로 저장되어있다면, 스왑영역(HDD)에 저장되어있음을 의미한다.
주의사항
페이지의 크기를 가장 신경써야한다.
프로세스가 많아질수록 페이지 테이블도 많아지므로, 프로세스가 실제로 사용할 수 있는 메모리 영역이 줄어든다.
실제로 메모리 관리자가 참조하는 테이블도 물리 메모리의 운영체제 영역에 존재한다.
페이지 테이블의 크기가 너무 커지면, 사용자 영역이 부족해질 수 있다. (페이지 크기를 적절하게 유지해야한다)
참고사항
세그멘테이션과 마찬가지로 페이지 테이블 베이스 레지스터는 운영체제가 컨텍스트 스위칭을 할 때마다 해당 프로세스로 업데이트해야한다.
세그멘테이션과 페이징 비교
페이지의 크기
세그멘테이션 : 프로세스마다 크기가 달라서 bound Adress를(크기를 나타내는 변수) 가지고 있어야한다.
페이징 : 모든 페이지의 크기가 동일해서 크기를 표현하는 변수가 필요하지 않다. (but, 내부 단편화가 발생)
단편화
세그멘테이션 : 외부 단편화가 발생한다 → 조각 모음으로 해결 가능하나, 오버헤드가 매우 크다.
페이징 : 내부 단편화가 발생하지만, 외부 단편화보다 크리티컬하지 않다.
영역의 분리
세그멘테이션 : 논리적인 영역으로 세그먼트를 나눈다. 세그먼트마다 크기를 다르게 나눌 수 있어서 코드, 데이터, 스택, 힙 영역을 분리할 수 있다.
페이징 : 페이지의 크기가 고정되어있어서 논리적인 영역으로 나눌 수 없다. 즉, 특정 영역과의 공유가 어려워진다.
메모리 접근 권한
💡 메모리 접근 권한 검사는 가상 주소에서 물리 주소로 변환될 때마다 일어난다. 권한을 위반한다면, 에러를 발생시키며 프로세스를 종료시킨다.
메모리 특정 번지수에 부여된 권한이다.
읽기, 쓰기, 실행 권한이 존재한다.
프로세스의 영역 별 접근 권한
코드 영역 : 읽기, 실행
프로그램 그 자체로, 수정되면 안 된다.
데이터 영역 : 읽기, 쓰기(선택)
일반변수, 전역변수, 상수가 저장되어있다. → 읽기 가능, 쓰기는 선택, 실행은 없음
스택, 힙 : 읽기, 쓰기
페이지드 세그멘테이션 기법
💡 세그멘테이션과 페이징을 혼합하여 장점을 취한 방식이다. 세그멘테이션의 장점 : 각 영역을 논리적으로 분할하여 다른 프로세스와 공유가 용이하며, 각 영역에 대한 메모리 접근 보호가 쉽다. (코드 영역만 공유하는 등) 페이징의 장점 : 메모리를 효율적으로 관리할 수 있다. (오버헤드가 적다.)
세그멘테이션 테이블과 페이징 테이블 두개를 모두 사용해야한다.
세그멘테이션 테이블에 권한 비트 열이 추가된다.
Base address는 Page number로 변경된다.
Bound address는 세그먼트의 페이지 개수로 변경된다.
과정
가상 주소가 들어오면, 몇 번 세그먼트인지 계산 ㅇ한다.
해당 세그먼트가 메모리 접근 권한을 위반하는지 검사한다.
위반했다면 종료시키고, 위반하지 않았다면 page number와 페이지 개수를 가져온다.
페이지 테이블에 접근해서 page number를 이용해 프레임을 가져온다.
물리 메모리 내 해당 프레임에 접근한 후 페이지 개수를 더해서 물리주소를 가져온다.
물리 메모리에 해당 프레임이 없다면, 스왑 영역에서 물리 메모리로 가져온다.
단점
물리 메모리에 접근하기 위해 메모리에 두 번 접근해야한다.
세그멘테이션 테이블 참조 / 페이지 테이블 참조
→ 현대 운영체제에서는 페이징과 페이지드 세그멘테이션을 적절히 섞어서 사용한다.
가져오기 정책
지역성 이론
💡 프로세스가 실행될 때, 코드 데이터 힙 스택 영역이 메모리에 모두 올라오는 것이 아니라, 필요한 모듈만 올라와서 실행된다. 디맨드 페이징은 지역성 이론을 기반으로 설계되었다.
도널드 커누스의 90:10 법칙
프로그램이 실행될 때 90%의 시간이 10%의 코드에서 보낸다는 이론이다.
지역성의 종류
공간의 지역성 : 현재 위치와 가까운 데이터에 접근할 확률이 높다.
시간의 지역성 : 최근 접근했던 데이터가 오래 전에 접근한 데이터보다 접근할 확률이 높다.
goto문을 쓰면 안 되는 이유
코드의 구조 파악이 어렵다.
지역성 이론을 위배하기 때문이다.(성능에 좋지 않기 때문에)
지역성 이론과 디맨드 페이징
조만간 쓰일 데이터만 메모리에 옮기고, 당분간 쓰지 않을 데이터를 스왑 영역에 옮기는 지역성 이론을 구현한 정책이다.
메모리 계층 구조와 접근 시간
메모리 계층 구조
레지스터 / 캐시 / 메인메모리 / 보조저장장치
레지스터 : CPU내에 존재하며, 1 사이클에 접근할 수 있다.
캐시 : 수 사이클 ~ 수십 사이클에 접근한다.
메인메모리 : 수백 사이클
보조저장장치 : 수백만사이클 (굉장히 오래 걸린다)
→ 메모리에 접근하는 시간이 보조 저장 장치로 갈수록 오래 걸린다.
디맨드 페이징
💡 스왑 영역을 보조 저장장치에 저장하는데, 성능 향상을 위해 스왑 영역으로 데이터를 이동시키는 것을 최소화시켜야한다.
스왑영역
가상메모리의 크기 = 물리 메모리 크기 + 스왑 영역
스왑인 : 스왑 영역에서 물리메모리로 데이터를 가져오는 것
스왑아웃 : 물리 메모리에서 스왑영역으로 데이터를 내보내는 것
페이지 테이블
가상주소가 주어지면, 메모리 관리자는 페이지 테이블을 참조하여 프레임 또는 스왑 영역의 위치를 알아내야한다. 이를 위해 페이지 테이블에는 여러 비트가 저장되어있다.
페이지 테이블 엔트리 : 페이지 테이블을 이루는 한 행 (프레임 넘버와 기타 정보들)
비트 종류
접근 비트 : 메모리에 읽기나 실행 작업을 했다면 1로 변경됨. (접근이 있었는가?)
변경 비트 : 쓰기 작업을 했다면 1로 변경됨. (데이터에 변경이 있었는가?)
유효 비트 : 물리 메모리에 존재하면 0, 스왑 영역에 있다면 1이 저장됨
권한 비트 : 메모리에 접근 권한이 있는지 확인하는 비트 (읽기, 쓰기, 실행 비트)
Page Fault
프로세스가 가상 메모리에 접근 요청을 했을 때, 물리 메모리에 없다면 페이지 폴트 인터럽트를 발생시킨다.
페이지 폴트가 발생하면, 보조 저장장치의 스왑 영역에 접근하고, 해당 프로세스는 대기 상태가 된다.
스왑 영역에 있는 데이터가 메모리로 올라온 후 대기 상태에 있던 프로세스가 다시 일을 시작한다.
가상메모리가 물리메모리 또는 스왑 영역에서 참조하는 경우
스왑이 필요 없는 경우
스왑 영역에 있는 데이터를 참조하는 경우
페이지 테이블 조회 후 스왑 영역에 있음을 알게 되었다.
물리 메모리의 빈 공간에 해당 프레임을 가져온다.
유효 비트를 0으로, 프레임 넘버를 해당 빈 공간으로 수정한다.
프로세스에게 데이터를 참조하게 해 준다.
물리 메모리가 가득 찬 상황
페이지 테이블 조회 후 스왑 영역에 있음을 알게 되었다.
물리 메모리에 비어있는 공간이 없다.
물리메모리에서 필요하지 않다고 판단하는 영역을 스왑영역으로 옮긴다.
옯겨진 프레임에 대해 페이지 테이블을 업데이트한다. (유효비트를 1로, 프레임 넘버를 스왑 영역 위치로)
비어있는 공간에 요청한 데이터를 가져오고, 페이지 테이블을 업데이트한다. (유효비트를 0으로, 프레임 넘버를 해당 위치로)
프로세스에게 데이터를 참조하게 해준다.
💡 스왑 인과 스왑 아웃을 할 때, 어떤 것이 적절한가를 판단하는 것은 페이지 교체 정책의 의해 결정한다.
교체 정책
💡 메모리가 가득 차서 Page Fault가 발생했을 때, 어떤 메모리를 스왑 영역으로 보낼지 결정하는 정책이다.
페이지 교체 정책의 종류
랜덤
페이지를 무작위로 선택해서 교체한다.
자주 사용되는 페이지가 선택되는 경우가 존재해서 성능이 좋지 않다.
자주 사용되지 않는다.
FIFO
가장 먼저 들어온 페이지를 가장 먼저 내보내는 정책이다.
자주 쓰이는 페이지가 먼저 들어온 경우 경제적이지 않다.
구현이 간단하고, 성능이 꽤 괜찮아서 변형해서 많이 쓰인다.
Optimal
앞으로 자주 쓰이지 않을 페이지를 보내는 방법이다.
이론적인 방법으로, 사실상 구현이 불가능한 방법이다. (앞으로 쓰일 페이지를 예측할 수 없으므로)
성능을 비교할 때 참조용으로 사용된다.
LRU (Least Recently Used)
최근에 사용이 가장 적은 페이지를 교체한다.
최근 사용한 데이터가 앞으로도 사용될 가능성이 높다는 지역성 이론에 기반한 방법이다.
Optimum 알고리즘과 가장 비슷한 성능을 띈다.
프로그램이 지역성을 띄지 않는다면, 성능이 떨어진다.
페이지 테이블 엔트리에 여러 비트와 페이지 넘버가 저장된다. 이 곳에 시간을 기록하면 너무 오래걸리며, 오래 지날 경우 오버플로우로 인해 정확한 성능을 내기 어렵다. 이에 시간이 아닌 접근 비트를 이용해 구현한다.
Clock Algorithm
LRU 구현과 문제점
LRU를 구현하기 위해서는 시간을 기록하는 많은 비트가 필요하다.
많은 비트가 있더라도, 시간이 오래 지나면 오버플로우가 발생하여 값을 올바르게 표현할 수 없다.
LRU와 유사하게 구현하는 것이 Clock algorithm이다.
구현 방법
접근 비트 하나만 사용하며, 페이지를 원형으로 연결한다.
접근 비트의 초깃값은 0이며, 페이지가 참조될 때 1로 설정한다.
일정 시간 간격마다 접근 비트를 0으로 초기화한다. (일정 시간마다 페이지의 참조 여부를 확인할 수 있다)
페이지를 포인터로 가리키는 포인터를 클락 핸드라고 부르며, 시계 방향으로 이동한다.
페이지 폴트가 발생하는 상황에서 클락 핸드는 현재 참조하고 있는 페이지의 접근 비트를 확인한다.
해당 비트가 1이라면 0으로 바꾸고, 다음 페이지로 이동한다.
반복하다가 접근 페이지가 0인 페이지를 본다면 스왑 영역으로 보낸다.
향상된 클락 알고리즘
접근 비트와 변경 비트를 확인한다.
스왑 영역으로 보내지는 우선순위
접근비트 0, 변경비트 0
접근비트 0, 변경비트 1
접근비트 1, 변경비트 0
접근비트 1, 변경비트 1
FIFO
빌레이디의 역설
Page Fualt를 줄이기 위해 메모리를 더 늘려서 Frame 수를 늘렸지만, 오히려 Page Fault가 많이 발생하는 현상
FIFO에서 발생한다.
LRU가 확실히 좋은 성능을 가지고 있으며, 빌레이디 역설도 발생하는데도 FIFO를 사용해야하는 경우가 있다.
바로! 하드웨어적으로 접근비트를 지원하지 않는 시스템!
이런 상황을 위해 2차 기회 페이지 교체 알고리즘이 고안된다.
2차 기회 페이지 교체 알고리즘
FIFO 방식에서 자주 사용되는 페이지에게는 한 번의 기회를 더 준다.
Page Fault 없이 페이지 접근에 성공했다면, 해당 페이지를 큐의 맨 뒤로 이동시켜 수명을 연장시켜주는 방법이다.
성능 : LRU > 2차 기회 페이지 교체 > FIFO
스레싱과 워킹셋
CPU 사용률
CPU 스케줄링의 목표 = CPU 사용률을 높이는 것
CPU 사용률 = 멀티프로그래밍 정도를 높이는 것 (동시에 실행하는 프로세스의 수)
즉, 동시에 실행하는 프로세스가 늘어난다면, 특정 프로세스가 I/O 작업으로 CPU를 사용할 수 없을 때, 다른 프로세스로 컨텍스트 스위칭을 해서 CPU의 사용률을 높일 수 있을 것이다.
멀티 프로그래밍의 정도가 높아지면, 그만큼 물리 메모리에 해당 프로세스를 할당해야한다.
물리 메모리의 크기에는 한계가 있으므로, 일부 메모리는 스왑 영역에 저장된다.
멀티 프로그래밍 정보가 늘어난 경우 발생하는 딜레마
제한된 물리 메모리에 모든 프로세스를 올린다.
당장 실행되는 프로세스를 제외하고, 스왑 영역에 저장된다.
잦은 Page Fault로 CPU 작업시간보다 Swap 작업 시간이 더 길어진다.
CPU 사용률이 떨어진다.
CPU 프로세스는 낮아진 사용률을 높이기 위해 더 많은 프로세스를 메모리에 올린다. (나중에는 사용률이 0에 가깝게 됨)
CPU 사용률을 높이고자 했지만, 오히려 떨어지는 상황을 스레싱이라고 한다.
스레싱과 워킹셋
스레싱의 근본적인 원인 : 물리 메모리 크기가 너무 작기 때문이다.
해결 방법
하드웨어적 해결
메모리의 크기를 늘린다
(참고) 그렇다면, 메모리의 크기를 무작정 늘리면 성능이 좋아지는가? (아니다!) 스레싱의 발생지점이 늦춰지기는 하지만, 기존 메모리에서 스레싱이 발생하지 않았다면 성능의 차이를 느끼기는 어렵다.
쳔재 메모리가 프로세스들이 작업하는데에 충분한 크기기 때문에 스레싱이 발생하지 않은 것이기 때문이다.
운영체제가 S/W적으로 해결
프로세스 별 페이지를 적절하게 할당한다.
즉, 프로세스가 실행되면 일정량의 페이지를 할당한다.
Page fault가 발생하면 더 많은 페이지를 할당한다.
page fault가 너무 적게 발생하면, 페이지 낭비라고 판단하여 페이지를 회수한다.
지역성 이론에 의거하여 어떤 페이지를 유지할지 결정한다.
현재 메모리에 올라온 페이지는 다시 사용할 가능성이 높다.
하나의 세트로 묶어 메모리에 올린다. (워킹셋이라 한다)
워킹셋은 프로세스가 준비 상태에서 실행 상태가 되는 컨텍스트 스위칭을 할 때 사용된다.
Last updated