Chapter 08 가상 메모리

운영체제는 주어진 메모리의 크기 아래서 프로그램을 작은 조각으로 나누어

그 중에 일부분만을 메모리에 적재하되, 적재 가능한 곳으로 비연속적으로(흩어) 넣어줌으로써,

사용자는 메모리에 대한 고민으로부터 벗어날 수 있게 된다.

(프로그램의 일부분만이 적재되기 때문에 보다 많은 사용자를 수용할 수 있고,

더 중요한 것은 모든 사용자가 메모리의 크기로부터 자유로울 수 있게 된다.)

 

가상 메모리(Virtual Memory)를 위해서는

▶ 우선, 모든 프로그램은 작은 조각(Block)들로 나뉘어지는데,

- 페이지(Page): 조각들의 크기를 모두 같도록 했을 때 한 조각

- 세그먼트(Segment): 조각들의 크기를 서로 다르게 했을 때 각각의 조각

* 조각의 크기 = 메모리와 디스크 사이에서 한 번에 전송되는 전송 단위.

 

가상 메모리의 관리에서,

- 페이지를 사용하는 시스템을 페이징 시스템,

- 세그먼트를 사용하는 시스템을 세그먼테이션 시스템 이라 부른다.

 

▶ - 가상 주소(Virtual Address): 프로그램에서 참조하는 주소

     - 실주소(Real Address): 실제 메모리 상의 주소

=> 가상 주소와 실 주소가 다르면 주소의 사상(mapping)이 필요하다.

*사상(Mapping): 실행 중인 프로그램에서 참조하는 주소가 실제 메모리에 있는 주소와 달라서,

                           메모리상의 주소로 변환이 필요할 때 하는 것

 

▶ 실주소 지정 시점

>> 컴파일 시

 - 프로그램이 실행될 때 참조하는 주소가 컴파일 될 때 지정

 - 참조하는 주소가 실주소이므로, 프로그램은 항상 메모리의 지정된 곳으로만 적재

                                                  ↓ (+ 융통성...)

>> 재배치

 - 컴파일 시에 주소를 프로그램의 첫 바이트를 0번지로 하여 번역

   (나머지 주소들은 프로그램의 처음부터 떨어진 바이트 수(offset)가 된다.)

 - 실행 시 재배치 레지스터에 프로그램이 적재되는 시작 주소를 넣어 실제 주소를 구할 수 있다.

 - 메모리에서의 위치를 적재될 떄마다 바꿀 수 있어서 융통성과 함께 메모리의 효율적인 이용이 가능

 

- 실행 시에 참조되는 주소 = 상대 주소(Relative Address)

- 실주소 = 시작 주소(Start Address)(=재배치 레지스터 값) + 상대주소

 =>  간단한 방식이지만, 프로그램이 전부가 통쨰로 연속적인 메모리에 적재되어야 함을 전제.

 

가상주소(실행 중인 프로그램에서 참조하는 주소)는 참조하고자 하는 명령어나 변수 등이

자신의 프로그램 내에서 몇 번째 조각에 있으며, 그 조각 내에서 어느 위치(Offset)에 있는지를 알려줌.

예) goto 10라는 명령어에서 10을 <3,5>(3번째 조각의 5번째 위치)로 대치.

이 값으로 사상과정을 거쳐 goto 해야 할 명령어의 실제 메모리 주소를 알게 됨.

(참고로, 대부분의 시스템에서 첫 번째 조각과 조각 내의 첫 번째 위치 값을 0으로 시작함)

 

페이징 (Paging)

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

▶ 메모리 역시 프레임(Frame)이라 불리는,

    페이지와 같은 크기로 나누어져 있으며 일련의 번호가 매겨져 있음.

- 한 프로세스의 전체 페이지들은 디스크에 저장되고, 이 중 몇 개가 메모리에

  비연속적으로 다른 프로세스들의 페이지들과 섞여 적재되는데, 프로세스의 실행이

  진행되는 과정에 따라 디스크와 메모리를 오가며 교체되는 단위가 페이지이다.

(- 일반적으로 페이지의 크기는 수 KByte 정도이며, 2^n으로 정한다.)

 

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

- 운영체제는 가상 주소를 실주소로 변환하기 위해 프로세스 당 하나의 페이지 테이블을 만들어 둠.

- 테이블의 테이블 크기 ∝ 해당 프로세스의 페이지 개수

(즉, 사상을 위한 정보는 페이지 당 하나씩 있어야 하므로 k개의 페이지를 가지는 프로세스의 페이지 테이블은 k개의 엔트리(Entry)로 구성되고 엔트리 하나의 크기는 보통 4byte 정도로 잡는다.)

- 한 프로세스에서 나뉘는 페이지들은 일련번호를 가지는데 페이지 테이블은 이 번호 순서대로 엔트리를 배치

- 테이블 에서 첫 번째 엔트리는 프로세스의 첫 번째 페이지를 위한 사상 정보를 가짐

- 엔트리에 들어있는 정보는 우선, 이 페이지가 메모리에 적재되어 있는가를 나타내는

  존재(Residence) 비트로서 적재된 경우 1, 아닐 경우 0의 값을 가짐

- 존재 비트의 값에 따라 1의 경우에는 적재되어 있는 프레임 번호를,

  0의 경우 이 페이지가 저장되어 있는 디스크의 주소를 나타내는 필드(Field)들을 각각 가지게 됨.

그 페이지가 있는 메모리의 Start Address를 넣지 않고, 그것이 들어있는 프레임 넘버를 넣어놓은 이유?

=> 프레임 넘버를 넣을 경우, 프레임 크기만큼의 비율로, 페이지를 찾아가기 위한 부분의 사이즈를 줄일 수 있다.

(if 프레임 넘버: 0~9 총 10개, else if 메모리 주소: 0~99 총 100개)

따라서, 그 프레임 앞에 있는 프레임 갯수 x 페이지 사이즈 = 그 프레임의 Start Address!

 

▶ 추가할 내용

- 각 프로세스의 PCB에 자신의 페이지 테이블 주소가 저장되어 있다.

  이 프로세스가 실행 상태가 될 때, 이 주소를 기준 레지스터에 넣어줌

- 한 번의 메모리 접근을 위해 실제로는 두 번 메모리 접근을 해야 됨

1) PMT에서 mapping을 위해 한 번,

2) 실제 Memory Access 한 번 ! 

=> Virtual Address가 우리에게 주는 혜택을 극대화하기 위해서는,

     '두 번의 메모리 접근에 걸리는 시간을 어떻게 하면 가급적 빠르게 할 것인가'가 중요!

 

■ TLB(Translation Lookaside Buffer)의 사용

- TLB는 고속 캐시의 일종 (Associative Memory  *일반 메모리x)

- 키(KEY) 값으로 찾고자 하는 워드를 동시에 접근하는 연관 메모리로서 검색이 빠른 반면 비싼 하드웨어

ㄴ 최근에 빈번하게 검색된 엔트리들을 TLB에 넣음

ㄴ 페이지 번호(p)를 키 값으로 동시 검색하므로 TLB에 저장되는 각 엔트리는 페이지 번호 순대로 보관할 필요가 없음

=> 메인 메모리는 메인 메모리대로 있고, TLB는 TLB대로 같이 사용해서

     두 번의 메모리 접근에 소요되는 time을 줄여보자~

 

▶ TLB에서의 검색 성공 확률을 적중률(hit ratio)이라 함

- 소량의 크기라도 90% 이상은 나올 수 있다는 실험결과들이 있고, 이런 이유로 TLB가 매력적

ex) TLB 검색과 메모리 접근에 각각 20과 100 나노 초(Nanosecond)가 걸리고, 적중률을 90%라 했을 떄,

     메모리를 접근하는데 걸리는 시간(실접근시간(Effective Access Time))은

     0.9 x 120 (TLB 접근 + 실주소 접근) + 0.1 x 220(TLB 접근 + 사상 테이블 접근 + 실주소 접근) = 130 나노 초

     가 되므로 TLB를 사용하지 않을 경우의 200 나노 초보다 빠름

 

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

▶ 페이지 보호

- 접근하고자 하는 페이지에 대해 읽기나 쓰기 작업을 어떻게 제한할 것인가와

  다른 프로세스의 주소 공간으로 침범하지 못하도록 하는 것

- 페이지 테이블 각 엔트리에 보호 비트(Protection Bits)를 두어 허용되는 접근 설정

 

▶ 공유

 - 사용자들이 흔히 하는 편집이나 컴파일 같은 작업은 프로그램 하나만 메모리에 두고

   여러 사용자가 같이 실행함으로써 메모리 공간 절약 가능

- 다수의 사용자가 한 부의 응용 프로그램을 공유하여 실행한다는 것은 

  공유 프로그램 내에서 각자의 실행 위치가 다른 한편, 각자의 데이터는 자신들의 주소 공간에 있도록 함

- 공유되는 프로그램은 코드의 내용이 실행 도중 변하지 않아야 하므로

  재진입 코드(Reentrant 또는 Pure Code)로 컴파일 되어 있음

- 프로그램은 명령어 페이지와 데이터 페이지로 나누어 지는데 명령어 페이지를 공유하여 사용

* 명령어 페이지는 실행 도중 address를 참조해 virtual address를 내놓기에 mapping을 해야 하고,

  데이터 페이지는 그럴 일이 없기에 둘을 나눠놓는 것이다!

 

페이징에서 사상 테이블의 구성 (참조) ㅡ space↓    (* 위에서 TLB ㅡ Time↓)

▶ 32 비트를 사용해 주소를 표현하는 시스템에서 하위 12 비트를 offset으로 사용한다면,

   페이지의 크기는 4Kbyte(2^12)가 되고 사상 테이블은 최대 100만 개(2^20)의 엔트리를 가질 수 있음

▶ 엔트리의 크기를 4Byte로 잡더라도 페이지 테이블의 크기는 4Mbyte가 되므로

   매우 큰 크기가 되어 메모리에 모두 저장하기에는 벅차게 되므로,

   페이지 테이블을 작게 나누어 필요한 부분만을 메모리에 적재하기 위해

   계층구조를 갖도록 구성할 수 있음

ex) 계층구조인 2단계 페이징을 예로 들어보자.

  위에서 말한 페이지 번호를 나타내는 20비트를 10비트씩 나누어

  상위 10비트를 바깥(또는 루트) 페이지 테이블의 엔트리 위치로,

  하위 10비트는 나누어진 테이블 내의 엔트리 위치를 나타내도록 하면 어떨까?

  메모리에 상주시키는 4Kbyte 크기의 루트 테이블과,

  같은 크기의 1024(2^10)개 페이지 테이블들의 선택적인 메모리 적재를 통해

  전부 적재해야 하는 부담을 줄일 수 있음

- 페이징은 고정 크기의 페이지로 메모리를 관리함으로써

  구현이 쉽다는 장점을 가지기 때문에 대부분의 시스템에서 채택되고 있음

- 프로그램의 마지막 페이지는 (평균적으로 페이지 크기의 반 정도의) 내부 단편화가 가능함

- 하나로 붙어 다녀야 효과적인 경우 (서브루틴, for문 또는 매트릭스(Matrix) 등),

  페이지 단위로 나누어져 일부만 적재되면 사상 시간이 길어지고 공유 또한 귀찮게 될 수 있음

=> 세그먼테이션 시스템

 

 

세그먼테이션(Segmentation)

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

   이런 논리적 단위를 세그먼트라 한다.

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

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

- 세그먼트 개수만큼의 엔트리를 가지는 세그먼트 테이블 필요

- 가상주소는 세그먼트 번호(s)와 세그먼트 내에서의 위치값(d)로 표현

- 존재 비트의 값에 따라 유효한 디스크 주소와 메모리 주소를 갖는 필드들이 있음

- 페이징과 다른 점은 메모리 주소 필드에 적혀 있는 값이 실주소임

- 세그먼트의 길이(Length)가 적혀 있는 필드가 있는데 이것은 세그먼트의 크기가

  서로 다음으로 인해 필요한 조치를 위해 사용

 

▶ 접근 제어 키(Access Control Key)

- 세그먼트의 실행을 제어할 때 사용하는 몇 개의 비트들을 구현에 따라 설정

- 읽기, 쓰기, 실행, 추가와 같은 작업을 각 비트를 1 또는 0으로 지정하고 그 조합으로,

  해당 세그먼트에 대해 정교하게 제어할 수 있음.

▶ 추가 고려 사항

- 세그먼테이션에는 내부단편화가 없음

- 세그먼트의 메모리 적재는 7장의 가변 분할에서의 배치(Fit) 기법을 사용

(=페이징과 달리 fit 기법 사용된다!)

ㄴ 외부 단편화 발생

- 세그먼트 테이블을 위해 TLB를 사용할 수 있음

-> 2단계 계층구조

-> 역 페이지 테이블 // 똑같이 적용된다!

 

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

▶ 보호

- 실주소를 위해 더해지는 위치 값(d)이 세그먼트의 길이 값을 초과하면,

  트랩을 통해 프로세스의 실행을 중지시켜 사용자 간의 메모리 보호가 가능

- 접근 제어 키를 사용하여 세그먼트 별로 허용되는 작업을 제어하여,

  사용자의 잘못된 접근으로부터 보호

▶ 공유

- 페이징과 같이 엔트리에 같은 주소 값을 가지도록 함

- 세그먼트의 장점이 드러남

* 공유해야 할 프로시저가 커서 몇 개의 페이지로 나누어진다면, 이 페이지들의 엔트리는

  공유하는 프로세스들의 페이지 테이블에서 모두 같은 위치에 있어야 하고 이것은 테이블의 구성을

  힘들게 만들 것이다. 또한, 페이지 크기와 정확하게 맞지 않을 경우, 공유할 필요 없는

  (또는, 공유해서는 안 되는) 부분이 공유 페이지에 포함될 수도 있다.

 

▶ 세그먼트의 장점

- 논리적 단위란 것은 단위 별로 수정하고 다시 컴파일해서 쓸 수 있음

- 프로그램의 일부의 변경 때문에 전부를 다시 링크하고 로딩하지 않아도 됨

~대신 페이징에 비해 좀 더 복잡, fit 기법 사용, length 필드를 받아서~ 이런 단점들이 있음.

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

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

- 프로그램을 먼저 세그먼트로 나눈 후, 각 세그먼트는 다시 페이지들로 나눔

- 각각의 세그먼트는 여러 개의 페이지들로 이루어질 것이고, 사상의 최종 단위는

  페이지이므로, 메모리는 페이지와 같은 크기의 프레임으로 구성

- 사상을 위해 세그먼트 테이블이 하나 필요하고, 세그먼트 테이블의 엔트리 개수만큼

  페이지 테이블이 필요해짐

- 가상주소는 세그먼트 번호(s), 페이지 번호(p) 그리고 페이지 내의 위치 값(d)으로 표현

- 세그먼트 테이블의 각 엔트리는 나누어진 자신의 페이지들을 위한

  페이지 테이블의 시작주소를 가지고 있음