[OS] Chapter 08. 가상 메모리

[OS] Chapter 08. 가상 메모리

누워서 보는 운영체제 이야기 - 김주균 교수님

---

▶ 시스템은 사용자 프로그램을 메모리의 어디에, 어떻게 넣을까로부터 메모리 수용 공간까지 알아서 해결해줌

• 운영체제는 주어진 메모리의 크기 아래서 프로그램을 작은 조각으로 나누어 그 중에 일부분만을 메모리에 적재하되, 그것도 적재가 가능한 곳으로 흩어(비연속적) 넣어줌으로써, 사용자는 메모리에 대한 고민으로부터 벗어날 수 있음
• 사용자들은 자신의 프로그램이 아무리 크더라도 아무 문제없이 메모리에 적재되어 실행된다는 확신을 가지게 됨
• 사실은 제한적인 크기지만 엄청나게 큰 메모리가 있는 것처럼 여겨지기 때문에 가상(Virtual) 메모리라고 부름

 

 

# 8.1 가상 메모리(Virtual Vemory)를 위해서는

▶ 모든 프로그램은 작은 조각들로 나누어지게 됨

• 페이지(page): 조각들의 크기를 모두 같도록 하면 한 조각을 페이지라 함
• 세그먼트(segment): 조각들의 크기를 서로 다르게하면 각각을 세그먼트라 함

▶ 페이지든 세그먼트든 그 크기가 메모리와 디스크 사이에서 한 번에 전송되는 전송 단위가 됨

• 블록(Block): 전송되는 전송 단위
• 가상 메모리 관리에서, 페이지로 나누었을 경우를 페이징, 세그먼트로 나누었을 경우를 세그먼테이션 시스템이라고 함

▶ 가상 메모리 관리를 위해 제일 먼저 해결되어야 할 부분은 주소의 사상(Address Mapping)

• 사상: 프로그램에서 참조하는 주소가 실제 메모리에 있는 주소와 달라서, 메모리상의 주소로 변환이 필요할 때 하는 것
• 가상 주소(Virtual Address): 프로그램에서 참조하는 주소
• 실주소(Real Address): 실제 메모리상의 주소

▶ 실주소 지정 시점

• 컴파일 시
  • 프로그램이 실행될 때 참조하는 주소가 컴파일될 때 지정된다는 것
  • 참조하는 주소가 바로 실주소이기 때문에, 프로그램은 항상 메모리의 지정된 곳으로만 적재되어야 함
  • ex) 고정 분할, 절대 로더
  • 단점: 적재 시의 융통성이 배제됨
• 재배치
  • 장점: 메모리에서의 위치를 적재될 때마다 바꿀 수 있어서 융통성과 함께 메모리의 효율적인 이용 가능
  • 전제: 프로그램 전부가 통째로, 연속적으로 메모리에 적재되어야 함 → 디스크와 메모리에서 같은 offset만큼 떨어져 있어야 함
  • 컴파일 시에 주소를 프로그램의 첫 바이트를 0번지로 하여 번역 → 나머지 주소들은 프로그램의 처음부터 떨어진 바이트 수(offset)가 됨
  • 실행 시 재배치 레지스터에 프로그램이 적재되는 시작 주소를 넣어주고 여기에 상대 주소 값을 더하면 실주소를 구할 수 있음
  • 실행 시 참조되는 주소: 프로그램 내에서 어느 정도의 위치에 있는지를 나타내는 상대주소(Relative Address)
  • 실주소: 메모리에 적재될 때의 시작 주소(Start Address) + 상대 주소 값 
  • but, 프로그램이 조각나고 이 조각들의 메모리 적재가 연속적이지 않다면 더 이상 쓸모가 없게 됨

▶ 가상 메모리로 관리 될 때, 프로그램들은 디스크에 조각난 모양으로 저장되고, 이 중 몇 개가 메모리에 비연속적으로 다른 프로그램의 조각들과 섞여 적재

• 메모리에 적재되어 있는 프로그램들이 다중 프로그래밍의 정도에 포함
• 번역된 프로그램 상의 주소. 즉, 가상 주소는 (p,d)의 형태를 가짐
  • p: 조각의 번호, d: 그 조각 내에서의 offset
• 실행 시, 가상주소(p,d)를 실제 주소로 바꾸는 주소 사상이 필요

디스크에 저장되는 조각들은 반드시 차례대로, 연속적으로 저장될 필요 X

붙일 수 있으면 사진과 같이 연속적으로 저장하는게 좋지만,

꼭 그럴 필요는 없으며 조각은 디스크의 어느 위치에나 저장 가능

조각을 합친 전체 프로그램이 디스크에 올라와있다는 것이 중요함

 

 

# 8.2 페이징

▶ 페이징을 위해서는 모든 프로세스들이 같은 크기의 조각들로 나뉘어야 하는데, 이때 한 조각을 페이지라고 함

▶ 메모리 역시 프레임(Frame)이라 불리는, 페이지와 같은 크기로 나누어져 있으며 일련의 번호가 매겨져 있음

• 한 프로세스의 전체 페이지들은 디스크에 저장되고, 이 중 몇 개가 메모리에 비연속적으로 다른 프로세스들의 페이지들과 섞여 적재되는데, 프로세스의 실행이 진행되는 과정에 따라 디스크와 메모리를 오가며 교체되는 단위가 페이지임
• 일반적으로 페이지의 크기는 수Kbyte 정도이며, 2^n배 크기로 잡음

▶ 페이지 사상 테이블(Page Map Table)

• 운영체제는 가상주소를 실주소로 변환하기 위해 프로세스당 하나의 페이지 테이블을 만들어 둠
• 테이블의 크기는 해당 프로세스의 페이지 개수에 비례
• 사상을 위한 정보는 페이지당 하나씩 있어야 하므로 k개의 페이지를 가지는 프로세스의 페이지 테이블은 k개의 엔트리로 구성되고 엔트리 하나의 크기는 보통 4byte 정도임
• 한 프로세스에서 나뉘는 페이지들은 일련 번호를 가지는데 페이지 테이블은 이 번호 순서대로 엔트리를 배치
• 테이블에서 첫 번째 엔트리는 프로세스 첫 번째 페이지를 위한 사상 정보를 가짐
• 존재비트: 이 페이지가 메모리에 적재되어 있는가를 나타내며 엔트리에 들어있음
• 존재 비트가 1인 경우 적재되어 있으며 적재되어 있는 프레임 번호를, 0의 경우는 적재되지 않았으므로 디스크의 주소를 나타내는 필드(field)들을 각각 가지게 됨

▶ 주소 사상(Address Mapping)

• 가상 주소: 페이지 번호(p)와 페이지 내에서의 offset(d)로 표시
• 존재비트가 0일 경우는 접근하고자 하는 페이지가 메모리에 없는 경우이며 이를 페이지 부재(page fault)라 함
• 사상 과정

페이지 테이블은 메모리의 커널 영역에 보관

프로세스의 페이지 테이블 시작주소는 페이지 테이블 기준 레지스터에 저장

기준 레지스터 값에 p를 더해 페이지 테이블에서 페이지 p의 사상 정보를 갖고 있는 엔트리를 찾은 후, 존재 비트를 확인

존재 비트가 1일 경우 p가 적재되어 있는 프레임(f)을 알 수 있으므로, 이 번호 값에 페이지 크기를 곱하면 메모리에서 이 프레임의 시작주소를 얻게 되고 여기에 d를 더하면 프레임 내에서 접근해야 할 워드의 주소. 즉, 실주소로 접근이 가능해짐

 

▶ 페이지 부재 처리 과정

• 페이지 부재(page fault): 존재 비트가 0일 경우 접근하고자 하는 워드를 포함하는 페이지가 메모리에 없음을 의미
• demand fetch(paging): 존재 비트가 0인 경우 실행을 계속하기 위해서는 먼저 디스크 주소로부터 이 페이지를 메모리에 적재해야 함. 그 다음, 이 엔트리의 존재비트를 1로 바꾸고 적재된 프레임 번호를 기입한 후 사상을 계속 진행하면 실주소를 얻게 될 것임
• 페이지의 메모리 적재는 프레임과 크기가 같으므로 빈 프레임만 있다면 그중에 아무거나 할당해주면 됨

▶ 프로세스와 페이지 테이블 그리고 메모리에 대해 잠시

• 각 프로세스 PCB(Process Control Block, 프로세스에 대한 모든 정보를 가진 자료구조)에 페이지 테이블 주소가 저장되어 있음 → 이 프로세스가 실행 상태(CPU를 받으면)가 될 때, 이 주소를 기준 레지스터에 넣음
• 한 번의 메모리 접근을 위해 실제로는 두 번의 메모리 접근을 해야됨 → 가상 메모리의 사용 이점을 극대화하기 위해서는 메모리에 두 번 접근하는 시간을 어떻게 줄일 것인가?가 중요하며 이를 위해 TLB를 사용함
  1. 메모리 내의 페이지 테이블에 접근
  2. 실주소 계산 후 해당 메모리 주소 접근

 

1) TLB(Translation Lookaside Buffer)의 사용

▶ TLB: 고속 캐시의 일종

• 키(Key) 값으로 찾고자하는 워드를 동시에 접근하는 연관 메모리로서 검색이 빠른 반면 비싼 하드웨어
• 최근에 빈번하게 검색된(많이 access된) 엔트리들을 TLB에 넣되, 페이지 번호(p)를 키 값으로 동시 검색을 하므로 TLB에 저장되는 각 엔트리는 페이지 번호도 함께 표시되어 있어야 함
• 모든 엔트리들은 페이지 번호 순대로 보관하고 있는 원본 페이지 테이블은 메모리에 있음

▶ 사상과정

• 가상주소의 p를 키 값으로 먼저 TLB부터 검색
• 엔트리가 있을 경우 검색되는 엔트리들의 페이지는 모두 메모리에 적재되어 있으므로 존재 비트를 확인할 필요가 없음
• TLB에서 p를 가지는 엔트리의 검색에 실패하면 메모리에 있는 페이지 테이블로부터 사상이 진행되어 실주소를 얻게되고, 이 엔트리는 TLB에 추가됨

▶ TLB의 크기만 충분하다면 한 프로세스의 페이지 테이블 전체 또는 여러 프로세스의 일부분씩을 같이 넣어둘 수 있음

• 후자의 경우는 엔트리들이 페이지 번호와 함께 프로세스 번호도 가지게 하고 검색 시의 키 값 역시 이 두 개를 사용해야 함

▶ TLB의 사용으로 실주소로의 접근 시간이 빨라지기 위해서는 원하는 에트리가 TLB에서 발견되는 확률이 높을수록 좋은 것

• 적중률(hit ratio): TLB에서의 검색 성공 확률
• 소량의 크기라도 90% 이상은 나올 수 있다는 실험 결과들이 있고, 이런 이유에서 TLB가 매력적이라는 것
• 예) TLB 검색과 메모리 접근에 각각 20과 100 나노 초가 걸리고, 적중률이 90%라고 했을 때, 실주소로 메모리를 접근하는데 걸리는 시간(실 접근 시간, Effective Access Time)은 다음과 같음

0.9 * 120(TLB 접근 + 실주소 접근) + 0.1 * 220(TLB 접근 + 사상 테이블 접근 + 실주소 접근) = 130
따라서 TLB를 사용하지 않을 경우의 200(사상 테이블 접근 + 실주소 접근) 나노 초보다 빠름을 알 수 있음

 

2) 페이지의 보호(Protection)와 공유(Sharing)

▶ 보호: 접근하고자 하는 페이지에 대해 읽기나 쓰기 작업을 어떻게 제한할 것인가와 다른 프로세스의 주소 공간으로 침범하지 못하도록 하는 것

• 페이지 테이블의 각 엔트리에 해당 페이지에 대한 보호 비트(Protection Bits)를 두어 허용되는 접근을 설정할 수 있음
• 예) 쓰기 작업에 대한 보호 비트의 값이 1이면 이 페이지에 대한 쓰기가 허용되는 것이며, 0일 경우 쓰기 시도는 보호에 위반되므로 트랩을 일으키게 됨

▶ 사상을 거쳐 접근 가능한 메모리 공간: 페이지들이 자리한 프레임 공간이 그 프로세스의 주소 공간임

• 프로세스가 사상을 거쳐 해당 페이지가 적재된 프레임의 시작주소를 알게 된 후, 여기에 더해지는 offset이 페이지의 크기를 넘게 되면 이것은 곧 다른 프레임으로의 접근을 의미하므로 트랩을 통한 보호가 이루어져야 함
• 따라서 페이징에서의 주소 공간 보호는 offset의 크기가 페이지의 크기를 넘지 않으면 안전함

▶ 공유: 사용자들이 흔히 하게 되는 편집이나 컴파일 같은 작업은 그 프로그램 한 부분만 메모리에 두고, 여러 사용자가 같이 실행해 줌으로써 메모리 공간을 절약하는 것

• 다수의 사용자가 한 부의 응용 프로그램을 공유하여 실행한다는 것은 공유 프로그램 내에서 각자의 실행 위치가 다른 한편, 사용되고 만들어지는 각자의 데이터는 자신의 주소 공간에 가지도록 한다는 것
• 공유되는 프로그램은 코드의 내용이 시행 도중 변하지 않아야 하므로 재진입 코드(Reentrant 또는 Pure Code)로 컴파일되어 있음
• 페이징에서의 공유: 프로세스 각자의 페이지 테이블에서 엔트리에 같은 프레임 번호를 가지도록 함으로써 구현. 즉, 프로세스들이 사상을 거쳐 같은 프레임을 접근하도록 함으로써 그 프레임에 적재된 페이지를 공유하게 되는 것
• 페이지는 프로그램 즉, 명령어 코드가 들어 있는 코드 페이지와 데이터 페이지로 나눌 수 있으며 명령어 페이지를 공유하며 사용함
  • 실행 도중 가상주소가 참조되어 사상이 요구되느냐의 여부와 관련이 있음
  • 코드 페이지는 명령어를 가지므로 가상 주소를 참조함
  • 데이터 페이지는 mapping 과정이 없음
• 코드 페이지가 공유되기 위해서는 재진입 코드여야 하고, 공유된 데이터 페이지에 대한 쓰기는 상호배제의 해결을 전제하여야 함

 

3) 페이징에서 사상 테이블의 구성

▶ 32비트를 사용해 주소를 표현하는 시스템에서 하위 12비트를 offset으로 사용한다면, 페이지의 크기는 4Kbyte(2^12)가 되고 사상 테이블은 최대 100만 개(2^20)의 엔트리를 가질 수 있음

▶ 엔트리의 크기를 4Byte로 잡더라도 페이지 테이블의 크기는 4Mbyte가 되므로 매우 큰 크기가 되어 메모리에 모두 저장하기에는 벅차게 되므로, 페이지 테이블을 작게 나누어 필요한 부분만을 메모리에 적재하기 위해 계층구조를 갖도록 구성할 수 있음

▶ 계층구조인 2단계 페이징

• 위에서 말한 페이지 번호를 나타내는 20 비트를 10 비트씩 나누어 상위 10 비트를 바깥(또는 루트) 페이지 테이블의 위치로, 하위 10 비트는 나누어진 테이블 내의 엔트리 위치를 나타내도록 하면 어떨까?
• 메모리에 상주시키는 4Kbyte 크기의 루트 테이블과, 같은 크기의 1024(2^10)개 페이지 테이블들의 선택적인 메모리 적재를 통해 전부 적재해야 하는 부담을 줄일 수 있음

▶ 2단계 페이징의 사상

▶ 역(Inverted) 페이지 테이블: 메모리에 고정 크기의 페이지 테이블 하나만 둠으로써 해결하는 방법

• 역 페이지 테이블은 메모리 프레임 수만큼 엔트리를 가지며, 테이블 내에서 엔트리의 순서는 프레임의 순서와 같음
• k번째 엔트리는 메모리의 k번째 프레임에 대한 사상 정보를 가지고 있는데, 빈 프레임인지 아닌지 나타내는 존재 비트와 함께 적재된 경우 어떤 프로세스의 몇 번째 페이지인지를 나타내게 됨
• 역 페이지를 사용할 때의 가상 주소는 페이지 번호(p), 위치(d)와 함께 이 페이지를 소유하는 프로세스(Pid)도 가져야 하는데, 이것은 사상을 할 때 프로세스 번호와 페이지 번호를 함께 사용하여 페이지 테이블을 검색해야 하기 때문임
• 참고로, 역 페이지 테이블을 사용하면 프레임마다 적재한 프로세스 번호를 가져야 하므로, 서로 다른 프로세스를 필요로하는 공유는 구현하기가 매우 힘듦

ex) 번호가 2인 프로세스가 페이지 번호 3과 위치 값 10으로 사상을 요구할 때

먼저 2와 3을 가지는 엔트리를 검색(최악의 경우 엔트리의 끝까지 검색)

발견된 엔트리의 역 페이지 테이블에서의 위치가 일곱번째라면

메모리의 일곱 번째 프레임에 2번 프로세스의 3번 페이지가 적재되어 있는 것이며, 여기서 위치 값 10을 더해 실주소를 알게되는 것임

 

▶ 페이징은 고정 크기의 페이지로 메모리를 관리함으로써 구현이 쉽다는 장점을 가지기 때문에 대부분의 시스템에서 채택되고 있음

• 하지만, 프로그램의 마지막 페이지는(평균적으로 페이지 크기의 반 정도의) 내부 단편화가 있게 됨

▶ 하나로 붙어 다녀야 효과적인 크기가 페이지 단위로 나누어져 일부가 적재되면 사상 시간이 길어지고 공유 또한 귀찮게 될 수 있음

• ex) for문, 매트릭스 등
• 결국, 논리적인 단위별로 프로그램의 조각을 다른 크기로 하는 것이 유용하다는 판단에서 사용되는 기법인 세그먼테이션이 필요

 

 

# 8.3 세그먼테이션(Segmentation)

1) 세그먼테이션

▶ 프로그램은 주(main) 프로그램, 프로시저, 함수, 스택 등의 논리적 단위로 이루어져 있음

• 이런 논리적 단위를 세그먼트라고 함

▶ 이런 서로 다른 크기의 세그먼트들이 모여 전체 프로그램을 구성하게 되며, 이런 단위로 적재하고 사상하는 기법을 세그먼테이션이라 함

▶ 사상은 크기가 다름으로 해서 요구되는 조치들을 제외하면, 페이징과 유사

• 세그먼트 개수만큼의 엔트리를 가지는 세그먼트 테이블 필요
• 가상주소는 세그먼트 번호(s)와 세그먼트 내에서의 위치 값(d)으로 표현
• 존재 비트의 값에 따라 유효한 디스크 주소와 메모리 주소를 갖는 필드들이 있음
• 페이징과 다른 점은 메모리 주소 필드에 적혀 있는 값이 실주소임
• 세그먼트 길이(Length)가 적혀 있는 필드가 있는데 이것은 세그먼트의 크기가 서로 다름으로 인해 필요한 조치를 위해 사용

▶ 제어 접근 키(Access Control Key)

• 세그먼트의 실행을 제어할 때 사용하는 몇 개의 비트들을 구현에 따라 설정
• 읽기, 쓰기, 실행, 추가와 같은 작업을 각 비트를 1 또는 0으로 지정하고 그 조합으로, 해당 세그먼트에 대해 정교하게 제어할 수 있음

▶ 사상 과정

▶ 추가 고려 사항

• 세그먼테이션에는 내부 단편화 없음
• 세그먼트의 메모리 적재는, 다양한 크기의 수용을 위해 배치(Fit) 기법이 사용되는데, 홀이라는 외부단편화가 생길 수 있음
• TLB, 테이블의 구성을 다단계 또는 역 페이지 등을 하는 것은 세그먼테이션에서도 똑같이 기능

 

2) 세그먼트의 보호(Protection)와 공유(Sharing)

▶ 보호

• 실주소를 위해 더해지는 위치 값(d)이 세그먼트의 길이 값을 초과하면, 트랩을 통해 프로세스의 실행을 중지시켜 사용자 간의 메모리 보호가 가능
• 접근 제어 키를 사용하여 세그먼트 별로 허용되는 작업을 제어하며, 사용자의 잘못된 접근으로부터 보호

▶ 공유

• 페이징과 같이 엔트리에 같은 주소 값을 가지도록 함
• 세그먼트의 장점이 드러남
  • 공유해야 할 프로시저가 커서 몇 개의 페이지로 나누어진다면, 이 페이지들의 엔트리는 공유하는 프로세스들의 페이지 테이블에서 모두 같은 위치에 있어야하고 이것은 테이블의 구성을 힘들게 만들 것
  • 또한, 페이지 크기와 정확하게 맞지 않을 경우, 공유할 필요 없는(또는, 공유해서는 안되는) 부분이 공유 페이지에 포함될 수 있음

▶ 세그먼트의 장점

• 논리적 단위란 것은 단위 별로 수정하고 다시 컴파일해서 쓸 수 있음
• 프로그램의 일부의 변경 때문에 전부를 다시 링크하고 로딩하지 않아도 됨

 

 

# 8.4 페이징을 사용하는 세그먼테이션

▶ 페이징의 편리함과 세그먼테이션의 논리적 장점을 함께가지기 위한 기법

• 프로그램을 먼저 세그먼트로 나눈 후, 각 세그먼트는 다시 페이지들로 나눔
• 각각의 세그먼트는 여러 개의 페이지들로 이루어질 것이고, 사상의 최종 단위는 페이지이므로, 메모리는 페이지와 같은 크기의 프레임으로 구성
• 사상을 위해 세그먼트 테이블이 하나 필요하고, 세그먼트 테이블의 엔트리 개수만큼 페이지 테이블이 필요해짐
• 가상주소는 세그먼트 번호(s), 페이지 번호(p), 그리고 페이지 내의 위치 값(d)으로 표현
• 세그먼트 테이블의 각 엔트리는 나누어진 자신의 페이지들을 위한 페이지 테이블의 시작주소를 가지고 있음

▶ 사상 방법