Memory Management

https://core.ewha.ac.kr/publicview/C0101020140425151219100144?vmode=f

반효경 [운영체제] 18. Memory Management 1

 

메모리 관리에 대해 배워보자.

 

Logical VS Physical Address

Logcial Address = Virtual Address 

프로그램 마다 가지고 있는 주소이다. 

각 프로세스마다 0번지부터 시작하는 주소를 각자 가지고 있다.

CPU 가 바라보는 주소는 logical address다. 

왜냐하면 프로그램이 실행되어서 물리적인 메모리에 올라가더라도 실제 instruction code안의 주소가 바뀌는 것은 아님 

(ADD 20 30 이 ADD 320 330으로 바뀌는 것이 아니라 여전히 ADD 20 30임)

즉 컴파일된 코드 자체에 들어가 있는 주소까지는 바꿀 수 없음. 시작위치가 바뀌는 것임

따라서 CPU가 메모리 몇번지에 있는 내용을 달라고 하면 그때 주소변환을 해서 물리적인 메모리 위치를 찾아서 읽어서 CPU에게 전달해야 한다.

 

Physical Address 

메모리에 실제 프로그램이 올라가는 위치다. 

아랫부분 : 운영체제 커널, 상위부분 : 여러 프로그램이 같이 올라가 있다. 

 

주소 바인딩 (주소 결정)

프로그램마다 0번지부터 시작하는 고유한 주소가 있지만 프로그램을 실행하기 위해서는 물리적인 주소로 올라가야 한다.

이 때 주소가 바뀌게 된다. 

 

Symbolic address -> logiclal address -> physical address

                                                          이 시점 ! 

 

symbolic address : 프로그래머가 프로그램을 만들 때는 변수 이름을 주고 변수에 값을 저장함. 또는 함수 이름을 가지고 함수를 호출함. 즉 프로그래머 입장에서는 숫자가 아닌 symbol로 된 주소를 사용한다. 이것은 symbolic address라 한다.

프로그램이 컴파일되면서 logical address가 된다. 

 

주소 바인딩 

Compile time binding 

- 컴파일 시에 주소 변환 발생 

- 논리적인 주소이지만 동시에 물리적인 주소임 -> absolute code 절대 코드라고 부른다 

- 메모리에 올라갈 위치를 바꾸고 싶으면 컴파일을 다시 해야한다

 

Load time binding 

- 실행이 시작될 때 주소 변환 발생 

- 컴파일해서 만들어진 코드는 재배치 가능한 relocatable  code다

- 실행 시에 비어있는 위치 어디든 올라갈 수 있는 코드 

 

Execution time binding 

- 프로그램이 시작된 이후에도 중간에 물리적인 메모리 주소가 바뀔 수 있는 방법 

- CPU가 메모리 주소를 요청할 때 마다 바인딩을 체크해 봐야 한다. (주소변환을 그때그때)

- 하드웨어적인 지원이 필요하다 (MMU)

 

프로그램을 컴파일해서 실행파일로 만들면 logical address로 바뀐다. 

심볼이던 A가 20번지, B가 30번지로 바뀐다.

이제 실행이 되기 위해서는 물리적인 메모리에 올라가야 한다. 

 

Compile time binding  

- 컴파일 시점에 이미 물리적인 메모리 결정 

- 즉 logical address와 같은 위치에 올려야 함 

- 비효율적임 . 다른 메모리 공간이 비어있어도 정해진 곳에만 올려야 함. 현재 컴퓨터에서 사용 X

- 과거에 컴퓨터 안에서 프로그램이 하나만 실행될 때는 이 방법을 사용했었음 

 

Load time binding 

- 프로그램이 시작되어서 메모리에 올라갈 때 물리적인 메모리 주소 결정 

 

Run time binding 

- 실행 시에 물리적 메모리 주소 결정 

- 다만 주소가 실행 도중에 바뀔 수 있음 

- 프로그램이 실행되다가 경우에 따라서 주소를 옮겨감 (메모리에서 쫓겨나고 다시 올림)

- 지금 사용하는 컴퓨터 시스템은 Run time binding을 지원함 

 

MMU 

Memory Management Unit : 주소변환을 지원해주는 하드웨어 

메모리관리에서는 일단 프로그램의 논리 주소가 통쨰로 물리 메모리에 올라가는 환경을 가정하고 설명한다. (실제로는 한번에 다 올라가지는 않음)

 

레지스터 2개를 활용한 MMU SCHEME

MMU는 레지스터 2개로 주소변환을 한다.

relocation register(base register)랑 limit register이다.

 

좌측 하단의 그림은 p1의 logical memory를 나타낸다. 

CPU가 346번지를 달라고 하면 시작 주소인 0번지부터 346번지 떨어진 곳을 요청한다.

그리고 실제 physical memory에는 14000번지부터 p1이 올라가 있다. 

시작위치인 14000과 논리주소 346을 더해서 14346을 구할 수 있다. 

 

relocation register에는 프로그램의 물리적 시작 주소를 저장해놓는다.

주소변환을 할 때 논리주소에 시작 주소를 더해서 물리적 주소를 얻는다.

 

limit register는 프로그램의 크기 3000을 담고 있다. 

이 프로그램이 악의적인 프로그램이라서 본인의 크기가 3000인데 CPU 명령을 통해 4000번지의 내용을 달라고 할 수도 있다. 18000번지가 되고 다른 프로그램이 존재하는 물리적 주소를 요청하게 된다. 

이런 경우는 주면 안된다. 이걸 막기 위해 limit register를 사용한다.

 

 

CPU가 논리 주소를 요청하면 

먼저 논리 주소가 limit register에 저장된 프로그램 크기보다 더 큰지 검사한다. 

값을 벗어나는 요청의 경우 trap(SW 인터럽트)이 걸린다. 프로세스가 하던 일을 멈추고 OS에게 제어권이 넘어간다.

OS가 프로그램을 응징(abort 하거나) 한다. 

넘지 않는다면 base register의 값을 더해 물리 주소로 변환해서 내용을 읽어서 CPU에게 전달해준다.

 

사용자 프로그램은 logical address만 다루고 physical address는 볼 수도 없고 알 필요도 없다.

 

용어 정리

Dynamic Loading

동적으로 프로그램을 메모리에 올리는 것이다.

프로세스 전체를 메모리에 미리 올리는 것이 아니라 해당 루틴이 불려질 때 메모리에 load하는 것이다. 

프로그램은 방어적으로 만들어진다. 

프로그램 전체의 메모리가 균일하게 사용되는게 아니다. 상당부분은 거의 사용되지 않는 오류 처리 루틴이다.

자주 사용되는 부분은 한정적이다. 

다이나믹 로딩은 운영체제에서 구현하지 않고 프로그래머가 직접 구현한다. 

다이나믹 로딩을 프로그래머가 쉽게 할 수 있도록 OS 라이브러리가 제공된다. 일일히 다이나믹 로딩을 어떻게 할 지 다 짜는 것은 아니다. 

프로그래머가 명시하지 않고 운영체제가 알아서 하는 것도 다이나믹 로딩이라는 말을 쓰긴 한다. 섞어 쓴다. 

Overlays

메모리에 프로세스의 부분 중 필요한 정보 만을 올려놓는 것이다. 하는 일 자체는 다이나믹 로딩이랑 같다.

하는 의도가 다르다. 

프로세스의 크기가 메모리보다 클 때 사용한다. 

프로그래머가 수작업으로 코딩한 것이고 Manual Overlay. 프로그래밍이 복잡하고 어렵다

OS의 지원이 없다. 

 

Swapping

프로세스를 메모리에서 하드디스크로 통째로 쫓아내는 것이다. 

쫓아내는 공간을 backing store 또는 swap area라고 부른다. (하드디스크 등)

 

 

중기 스케쥴러가 Swap out시킬 프로그램을 결정한다. swapper라고도 부른다.

메모리에 너무 많은 프로그램이 있으면 비효율적이어서 중기스케쥴러가 골라서 swap out한다.

CPU 우선순위가 낮은 프로그램을 swap out 시킨다.

 

Compile time binding이나 Load time binding을 사용하면 swap out 후 swap in 될 때 같은 물리적 주소에 올려야 한다. 

스와핑이 효율적이려면 Run time binding이 좋다. 

swap out을 당해서 쫓겨났어도 다른 메모리 위치가 비어있어도 올라갈 수 있는 것이다. 

 

스와핑은 많은 양의 데이터를 한꺼번에 올리고 내린다. 

swap time은 따라서 transfer time의 비중이 크다. transfer time은 실제 데이터를 전송하는 swap 되는 양에 비례하는 시간이다. 

 

일부 페이지가 쫓겨 나는 것도 페이지가 swap out 됐다 라는 말을 쓰기도 한다.

원칙적으로는 프로그램의 주소공간 전부가 쫓겨나는 것을 swap out이라 한다. 

 

Dynamic Linking 

프로그램을 컴파일 한 후 여러 군데에 있는 컴파일 된 파일을 링킹해서 실행 파일을 만든다. 

다이나믹 링킹은 링킹을 실행 시간까지 미루는 기법이다. 

 

static linking 

- 라이브러리라 프로그램의 실행 파일에 포함 

- 실행 파일 크기가 커짐 

- 동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로 메모리 낭비 

 

dynamic linking 

- 라이브러리가 실행 시 link 됨 

- 실행파일에는 라이브러리를 찾을 수 있는 stub이라는 작은 코드를 둠 

프로그램이 실행되다가 라이브러리를 호출하면 라이브러리가 어디 있는지 찾는다 

필요하면 메모리에 올리고 이미 올려놨다면 그 주소로 가서 라이브러리를 실행한다. 

 

예) printf 라이브러리 함수 

dynamic linking을 하면 내 프로그램에 printf의 위치를 찾는 코드만 내 실행파일에 있다.

이미 메모리에 pritnf 를 미리 올려놓았으면 공유해서 사용 가능하다.

리눅스 shared object, 윈도우즈 dynamic linking 파일이 shared library 파일이다.

 

 

Allocation of physical memory

물리적인 메모리의 낮은 주소 부분에는 항상 OS가 상주한다. 

높은 주소 영역에는 사용자 프로그램이 올라간다. 

 

사용자 프로세스 영역을 연속할당, 불연속할당 2가지 방법으로 관리할 수 있다. 

프로그램이 메모리에 올라갈 때 통째로 올라가는 것이 연속할당이다.

불연속할당은 프로그램의 주소공간을 잘게 잘라서 일부는 여기 일부는 저기 할당하는 것이 불연속 할당이다.

현대 시스템에서는 불연속 할당을 사용한다. 

프로그램의 주소 공간을 같은 크기의 페이지로 잘라서 사용하는 것을 페이징 기법이라 한다.

연속할당

연속할당도 2가지로 나눌 수 있다.

고정 분할 방식과 가변 분할 방식이다.

고정 분할 방식은 프로그램이 들어갈 사용자 메모리 영역을 미리 파티션으로 나눠놓는 것이다.

가변 분할 방식은 메모리 영역을 미리 나눠놓지 않는 것이다. 

 

위에서 보면 고정 분할 방식은 분할 4개로 미리 나눠 놓았다.

낭비되는 메모리 조각 외부 조각과 내부 조각이 발생한다. 

외부 조각은 프로그램 B를 분할에 올리고 싶은데 B의 크기보다 분할의 크기가 작아서 분할이 사용되지 않은 것이다.

내부 조각은 분할에 프로그램을 넣고 공간이 남은 것이다. 

 

가변 분할 방식을 사용하면 프로그램이 실행될 때 마다 차곡차곡 메모리에 올리는 방식이다. 

B가 끝나고 D가 들어오는데 B가 쓰던 공간에 D가 못들어가서 외부 조각이 생긴다. 

프로그램 크기가 균일하지 않기 때문이다.

 

가변 분할 방식을 사용하면 메모리에 hole이 생긴다. 

가용 메모리 공간 hole이다. 

hole들이 여기저기 산발적으로 생긴다. 

 

Dynamic Storage Allocation Problem

어느 Hole에 새로운 프로그램을 집어넣을 것인가?크

가변 분할 방식에서 생기는 Dynamic Storage Allocation Problem이라 한다. 

가변 분할에서 size n인 요청을 만족하는 가장 적절한 hole을 찾는 문제이다.

3가지 알고리즘이 있다.

 

First fit 

제일 처음 발견되는 크기가 n 이상인 hole에 그냥 넣는다

hole을 다 살펴볼 필요가 없다. 

Best fit 

hole을 다 살펴보고 프로그램 크기랑 가장 잘 맞는 hole에 올려 놓는다. 

크기가 n 이상인 hole 중 가장 작은 hole에 넣는다. 

작은 hole이 여러개 생성된다. 

Worst fit 

가장 큰 hole에 넣는다 

모든 홀을 탐색해야 한다. 

큰 홀은 나중에 써야 될수도 있는데 이렇게 써버리면 안좋다.

큰 hole들이 생성된다. 

 

first fit, best fit이 worst fit보다 속도, 공간 이용 측면에서 효율적이다.

first fit은 hole을 찾는 오버헤드가 없고 best fit은 가장 적당한 hole을 찾아서 미래를 위해 좋다. 

 

compaction

외부 조각 hole들을 한 군데로 밀어서 큰 hole로 만드는 것이다.

hole의 크기가 작아서 사용이 안되는 외부 조각 문제를 해결할 수 있다.

메모리에서 디스크 조각 모음을 하는 것이다. 비용이 많이 드는 호락호락하지 않은 방법이다.

전체 프로그램의 바인딩을 고려해야 하기 때문이다. 

run time binding이 지원되어야 할 수 있다.

 

전체를 다 미는 것 보다는 최소한의 이동으로 큰 hole을 만들 수 있으면 좋다. 

어떤 프로그램을 이동시킬 지 결정하는 것도 매우 복잡하다. 

 

불연속 할당 

 

현대 OS에서 사용하는 방법은 지금까지 설명한 연속 할당 방법이 아닌 불연속 할당 방법이다. 

불연속 할당은 Paging과 segmentation 기법으로 나뉜다. 

 

 

페이징은 프로그램을 구성하는 주소공간을 같은 크기의 페이지로 자르는 것이다. 

같은 크기로 잘라서 페이지 단위로 물리적인 메모리에 올려놓는 것이다. 또는 backing store에 내리거나.

 

물리적인 메모리의 사용자 프로그램 공간도 페이지 하나가 들어갈 수 있는 크기로 잘라 놓는다.

이것은 page frame이라 한다. 

페이지 프레임 하나하나에 페이지들이 올라갈 수 있다.

 

페이징 기법을 쓰면 hole들의 크기가 균일하지 않아서 발생하는 문제나 hole들을 compaction하는 문제가 발생하지 않는다. 어차피 frame이 비어서 어느 페이지든 올라갈 수 있기 때문이다. 

 

대신 단점으로는 주소변환이 복잡해진다. 단순히 시작주소만 더해서 주소변환을 하는 것이 아니라 각각의 페이지가 물리적인 메모리의 어디에 올라가 있는지 확인을 해야하기 때문이다. 

 

Segmentation 기법은 프로그램의 주소공간을 같은 크기로 자르는게 아니라 의미있는 단위로 자르는 것이다. 

프로그램의 주소공간이 code, data, stack 세가지의 의미있는 공간으로 구성된다.

이렇게 자를 수도 있다 (함수마다 자른다거나)

의미단위로 자르는 거기 때문에 크기가 균일하지는 않다. 

연속 할당에서 발생하는 문제들이 segmentation 기법에서도 동일하게 발생한다. 

 

 Paging

주소공간을 동일한 크기의 페이지로 나눈다. 

일부는 backing store에 있고 일부는 물리적인 메모리에 올라갈 수 있다.

페이지 단위로 불연속적으로 메모리에 올라갈 수 있다. 

물리적 메모리 또한 페이지 프레임으로 나뉜다. 

OS는 비어있는 페이지 프레임이 어디인지 관리하게 된다.

주소변환이 페이지 단위로 이루어져야 하기 때문에 페이지 테이블을 사용한다. 

프로그램을 구성하는 주소공간이 여러개로 구성되는데 각각의 페이지가 어디 올라가있는지 테이블에 표시한 것이다. 

 

외부 조각은 발생하지 않는다. 같은 크기로 잘랐기 때문에

내부 조각은 발생할 수 있다. 프로그램의 크기가 반드시 page 크기의 배수라는 보장이 없기 때문이다. 

맨 마지막 조각은 페이지보다 작을 수 있기 때문이다. 이 때 내부 조각이 약간 생긴다. 

 

페이징 예시

페이지 테이블은 각각의 논리적인 페이지가들이 몇번째 물리적인 페이지 프레임에 들어가 있는지 표시하는 테이블 

페이지 개수만큼 테이블 엔트리가 존재하고 각 엔트리에는 그 페이지가 몇번 물리적인 프레임에 들어가 있는지 보여준다.

0번 페이지는 1번 프레임에 올라가 있다. 

엔트리의 크기가 미리 정해져 있어서 일일히 다 검색할 필요가 없다. 

그냥 n번째 페이지를 주소변환 하고 싶으면 위에서부터 n번째로 가면 된다.

즉 인덱스를 이용해서 곧바로 접근할 수 있는 자료구조이다. 

 

 

주소에서 앞부분 p가 페이지 번호가 되고 뒷부분 d가 페이지 내에서 얼만큼 떨어져 있는지 나타내는 offset이다. 

p를 페이지 프레임 번호 f로 바꿔주면 주소변환이 끝난다. 

 

뒷부분 d는 내부에서 상대적인 위치이므로 변하지 않는다. 

페이지 테이블의 구현 

페이지 크기는 보통 4kb이다. 

실제로는 페이지 테이블의 엔트리가 1000000개정도 필요하다.

페이지 테이블의 용량도 커져서 CPU의 레지스터에 들어갈 수가 없다.

심지어 프로그램마다 페이지 테이블이 있다.

 

페이지 테이블을 따라서 메인 메모리에 집어넣는다.

메모리 접근을 위해서는 주소변환을 하고 접근해야 한다. 

주소변환을 하려면 페이지 테이블에 접근해야 하고 페이지 테이블은 메모리에 있다.

따라서 모든 메모리 접근 연산에는 2번의 메모리 접근이 필요하다.

 

2개의 레지스터는 각각

Page table base register PTBR 이 page table을 가리키고 (메모리 상 페이지 테이블의 시작 위치)

Page table length register PTLR이 페이지 테이블 크기를 보관한다.

 

모든 메모리 접근마다 2번 메모리 접근 해야 해서 비용이 크다. 시간 2배 걸림

이것을 해결하기 위해 TLB라는 translation look-aside buffer라는 별도의 HW를 사용한다.

주소 변환을 위한 별도의 캐시가 TLB이다.

page table에서 빈번히 참조되는 일부 엔트리를 캐싱하고 있다.

메인메모리보다 접근이 빠른 hw로 구성되어 있다.

CPU가 논리적인 주소를 주면 메모리 상의 page table 접근 전에 tlb를 먼저 검색한다.

있으면 TLB를 통해 주소변환을 한다. 

TLB에 없으면 페이지 테이블을 통해 일반적인 주소변환을 한다. 

TLB는 페이지 테이블의 일부 정보만 담고 있는 것이다. 

 

TLB는 모든 페이지를 갖고있는 것이 아니기 때문에 프레임번호만 가지고 있으면 안된다.

p와 f를 쌍으로 가지고 있어야 한다. 

 

그리고 TLB를 다 찾아봐야 찾으려는 정보가 있는지 없는지 알 수 있다.

즉 특정 항목만 검색하는것이 아닌 전체를 search한다.

시간 소요가 큰데 이를 막기 위해 TLB는 보통 parallel search가 가능한 assosiative register를 사용한다.  

 

page 테이블은 각각의 프로세스마다 존재한다. 

따라서 TLB의 정보는 context switch때 flush 된다. 

effective access time

실제 메모리 접근하는 시간 EAT은 어떻게 되는가?

TLB를 접근하는 시간 입실론은 메인 메모리 접근시간 1보다 작다.

TLB로부터 주소변환이 되는 비율을 alpha라고 하면 

성공할 경우 (1+입실론)alpha이고

실패할 경우 (2+입실론)(1-alpha)이다(페이지 테이블 접근 1, 실제 데이터 접근 1, tlb 접근 입실론)

alpha는 1에 근접하고 입실론은 매우 작으므로 2+입실론-알파는 page table만 있을 때 걸리는 시간 2보다는 훨씬 작다.

two level page table

안쪽 페이지 테이블과 바깥쪽 페이지 테이블이 있다

2단계 페이지 테이블은 안쪽 페이지 테이블, 바깥쪽 페이지 테이블이 있다.

페이지 테이블에 두번접근해야 하니까 시간은 오히려 더걸린다.

2단계 페이지 테이블을 쓰는 이유는 공간을 줄이기 위해서다.

 

현재 컴퓨터는 주소체계가 매우 큰 프로그램을 지원한다. 

프로그램마다 가지고 있는 가상 메모리의 크기가 얼마까지 가능한지는 주소체계를 몇비트 주소체계를 쓰는지에 따라 결정된다. 

32bit면 0부터 2^32-1까지 프로세스의 가상 주소를 표현할 수 있다. 

2^32 byte = 4GB의 프로세스 크기 (최대)

2^10 = Killo, 2^20 =Mega, 2^30 = Giga

페이지 하나의 사이즈가 4Killo=2^12byte라 하면 총 2^20 페이지, 즉 1M개로 나눠진다.

따라서 page table 엔트리도 1M개가 필요하다.

하나의 엔트리는 4byte정도 된다. 

띠리서 프로그램 마다 4M의 페이지 테이블이 필요하다. 

이걸 메모리에 다 넣자니 낭비가 심하다. 

심지어 메모리 주소공간 중 실제 프로그램이 사용하는 공간은 지극히 일부분이다. 

따라서 1단계 페이지 테이블은 공간낭비가 심하다.

 

이런 문제를 해결하기 위해 2단계 페이지 테이블을 사용한다.

바깥쪽 페이지 테이블 번호 p1, 안쪽 페이지 테이블 번호 p2를 사용한다.

2단계 page table에서의 주소변환

 

논리적인 주소가 p1,p2,d로 구성된다.

 

p1 : 바깥쪽 페이지 테이블에서 p1번째 엔트리로 이동한다. 페이지 번호

바깥쪽 테이블 엔트리 하나 당 안쪽 페이지 테이블 하나가 만들어진다. 

즉 바깥쪽 페이지 테이블의 값은 안쪽 페이지 테이블이 어떤 건지 가리킨다. 

p2 : 안쪽 페이지 테이블에서 p2번째 엔트리로 이동한다. 

안쪽 테이블 엔트리의 값은 물리적인 페이지 프레임의 번호이다. 

d : 페이지 프레임 번호를 얻어서 해당 페이지 프레임에서 d만큼 offset 이동하면 원하는 물리적 주소를 찾을 수 있다.

 

안쪽 페이지 테이블의 크기는 페이지 크기와 같다 4kb가 된다.

엔트리 하나당 4byte이므로 안쪽 페이지 테이블 하나의 엔트리는 1k개가 된다.

 

two level paging example

32bit 주소체계에서 각 내용은 몇 bit가 되어야 할까?

페이지 하나의 크기 : 4kb = 2^12byte

2^12를 구분하기 위해서는 12bit가 필요하다. 즉 offset d는 12자리가 된다. 

 

p2는 안쪽 페이지 테이블에서 몇번째 엔트리인지 구분하는 수이다. 

안쪽 페이지 테이블은 1k=2^10개의 엔트리를 가진다. 따라서 10bit만큼 필요하다.

 

그리고 나서 32bit에서 22bit를 뺀 10bit가 p1을 위한 크기가 되는 것이다. 

 

만약 64bit 주소체계를 쓴다면? 

혼자 생각해보자..

 

그런데 2단계 페이지 테이블을 쓰면 공간적으로 이득이라고 했는데, 

안쪽 페이지 테이블은 1K개의 엔트리를 갖고, 안쪽 페이지 테이블이 1K개 있으니까

총 1M의 페이지 테이블 엔트리가 필요하다. 1단계 페이지 테이블 쓸 때랑 테이블 엔트리 개수가 똑같이 필요하다.

그리고 바깥 페이지 테이블 까지 있으니 공간도 결국 더 든다!

시간도 손해, 공간도 손해다. 왜 쓰는걸까 ??

 

 

프로그램을 구성하는 페이지 중 상당부분은 사용이 안 된다

하지만 사용이 안되는 페이지더라도 1단계 페이지 테이블을 쓸 때는 최대 logical memory의 크기만큼 페이지 테이블을 만들어야 한다. 왜냐하면 위에서부터 엔트리를 세는 주소 방식이기 때문이다. 중간이 빌 수가 없다. 

 

하지만 2단계 페이지 테이블을 쓰면 그것을 해소할 수 있다.

바깥쪽 페이지 테이블은 다 만든다.

사용이 안되는 페이지에 대해서 안쪽 페이지 테이블을 안 만들면 된다. 

포인터 = null 상태로 놓는 것이다. 

사용되는 페이지에만 대해서 안쪽 페이지 테이블을 만들어주면 된다. 

그래서 공간적으로 이득인 것이다. 

 

다단계 페이지 테이블 

다단계 페이지 테이블도 있다.

페이지를 위한 공간을 많이 줄일 수 있지만, 한번 주소변환을 하려면 페이지 테이블을 여러번 거처야 한다. 

예를 들어 4단계 페이지 테이블이라면 주소변환을 위한 메모리 접근 4번, 실제 메모리 접근 1번 총 5번의 메모리 접근이 필요하다.  시간 overhead가 크다.

 

하지만 주소변환을 위한 캐시 메모리 TLB에 대해 위에서 배웠다.

TLB를 통하면 시간이 그렇게 오래 걸리지 않는다. 

메모리 접근 시간이 100ns, TLB 접근 시간이 20ns라 가정하자.

TLB hit ratio가 98%인 경우 (TLB를 통해 직접 주소변환이 되는 비율이 98%)

eat = 0.98(100+20) + 0.02(500+20) = 128ns

= 0.98(실제 메모리 접근 + TLB 접근) + 0.02(실제 메모리 접근 1회,주소변환 메모리 접근 4회 + TLB 접근 1회(없는지 확인하기 위해) 

주소 변환을 위해 28ns만 소요되는 효과이다. 

 

Valid (v)/Invalid (i) bit in a page table

 

사실은 부가적인 bit가 페이지 테이블의 엔트리마다 저장된다. 그것이 valid, invalid bit이다.

이 프로그램은 5page까지 있다. 따라서 페이지 테이블의 6,7 엔트리는 사용하지 않는다.

그렇다면 왜 6,7 엔트리가 존재하냐?  

프로그램의 주소공간이 가질 수 있는 maximum size만큼 페이지 테이블 엔트리는 생겨야 하기 때문이다. 

페이지 테이블이 만들어지긴 했지만 사용되지 않는 값이기 때문에 invalid로 표시한 것이다.

왜냐하면 이렇게 표시를 안하면 이 페이지가 실제 쓰이는 것인지 아니면 0번 페이지 프레임을 가리키는지 알 수가 없기 때문이다. 

invalid이면 해당 페이지가 사용되지 않거나 , 현재 메모리에 올라가 있지 않고 backing store에 있는 것일수도 있다.

 

즉 valid, invalid의 의미는 이렇다. 

- valid : 해당 주소의 frame 그 프로세스를 구성하는 유효한 내용이 담겨 있음 

- invalid : 해당 주소의 frame에 유효한 내용이 없음 - 접근 불허 

프로세스가 그 주소 부분을 사용하지 않거나, 페이지가 swap area에 내려가 있는 경우 

 

protection bit

protection bit도 있다.

- page에 대한 접근 권한 

페이지 중에는 프로그램의 코드를 담고 있는 페이지도 있고, data, stack을 담고있는 페이지도 있다.

code는 내용이 바뀌면 안된다. 원래 있는 내용을 CPU에서 읽어서 명령을 실행해하기만 해야 한다. 

따라서 code는 read only가 되어야 하고, data stack은 read-write 권한을 다 줘야 한다.

protection bit는 따라서 그 페이지에 대해 읽기권한, 쓰기권한이 있는지 나타낸다. 연산에 대한 권한이다

 

Inverted page table

페이지 테이블의 문제는 메모리 공간을 많이 차지한다는 것이다.

페이지 테이블이 큰 이유는 

- 모든 프로세스 별로 그 논리적 주소에 대응하는 모든 페이지에 대해 페이지 테이블 엔트리가 있어야 한다. 

- 메모리에 대응하는 페이지가 있는지 없는지 간에 페이지테이블에는 엔트리가 존재한다. 

 

inverted page table

 

원래 페이지 테이블을 역발상으로 뒤집어 놓은 것이다.

각 프로세스마다 페이지 테이블이 존재하는 것이 아니라 시스템에 페이지 테이블이 하나가 존재한다. 

페이지 테이블의 엔트리가 프로세스의 페이지 개수만큼 존재하는 것이 아니고 물리적인 메모리의 프레임 개수만큼 존재한다.

즉 페이지 테이블의 f번째 엔트리는 물리적 메모리의 f번째 페이지 프레임을 나타낸다.

페이지 테이블의 f번째 엔트리에는 물리적 메모리의 f번째 페이지 프레임에 들어가는 페이지의 논리적인 주소가 들어가 있다. 

주소변환은 논리적 주소 -> 물리적 주소로 바꾸는 건데.. 물리적 주소 -> 논리적 주소를 얻는 테이블이다.

이 테이블을 통해 주소변환을 하려면 어떻게 해야할까??

논리적 주소 p가 물리적 메모리의 어디에 올라가 있는지 알려면 페이지 테이블을 다 찾아보면서 f번째 엔트리에서 p값이 나오면 p가 f번쨰 프레임에 올라가 있다고 알 수 있다. 

테이블의 묘미는 인덱스를 통해 바로 검색할 수 있는게 장점인데 inverted page table을 그런 장점이 없다.

 

이거 왜쓸까 그러면 ?

페이지 테이블을 위한 공간을 줄이기 위함이다. 시스템 안에 하나만 존재해서 공간을 많이 줄일 수 있다. 

대신 시간적인 overhead가 늘어난다. 페이지 테이블을 전부다 search 해야 주소변환이 가능하기 때문이다.

 

그리고 페이지 테이블에 pid라는 것도 저장해야 한다. 어떤 프로세스의 페이지인지도 알아야 하기 때문이다.

즉 pid 프로세스의 p번째 페이지 이렇게 정보를 저장한다. 

즉 주소변환은 pid랑 p를 같이 받아서 페이지 테이블에서 몇번쨰 인지 찾아서 변환해주면 된다.

일반적으로 시간을 줄이기 위해 assosiative register를 사용해서 페이지 테이블의 엔트리를 병렬적으로 검색할 수 있게 한다.

 

Shared page

프로그램을 구성하는 페이지 중에는 다른 프로그램하고 공유할 수 있는 페이지가 있다.

프로세스 p1,p2,p3가 같은 코드를 가지고 프로그램을 돌린다면?

프로그램의 코드 부분은 같은 내용을 써도 된다. 

이렇게 share 할 수 있는 코드를 shared code라 한다. (또는 re-entrant code, pure code)  

shared code는 하나의 copy만 물리적인 메모리에 올릴 수 있다.

같은 frame에 올리고 mapping 시킨다. 

 

shared code 기법을 쓰려면 2가지 조건을 충족해야 한다.

1. read-only로 페이지를 설정해야 한다

2. shared code는 모든 프로세스의 논리적 주소 상에서 같은 위치에 있어야 한다.

왜냐하면 코드 안에 써있는 주소값은 변하는게 아니기 때문이다.

 

Segmentation

프로세스를 구성하는 주소공간을 의미 단위로 쪼갠 것이다. 예를 들자면 code, data, stack각각이 segment가 된다.

또는 함수별로 segment를 구성할 수도 있다.

 

Segmentation 아키텍쳐

segmentation에서는 논리 주소를 <segment-number, offset> 형태로 구성한다.

각 segment별로 서로 다른 물리 주소에 올라갈 수 있기 때문에 세그먼트 별로 주소변환을 해야 한다.

따라서 세그먼트 별로 세그먼트 테이블을 둔다. 

 

세그먼트 테이블 

- 각 테이블 엔트리는 base와 limit을 가짐

- base : 세그먼트의 시작 물리 주소 

- limit : 세그먼트의 길이

Segment table base register STBR

- 물리적 메모리에서 세그먼트 테이블의 위치

Segment table length register STLR

- 프로그램이 사용하는 세그먼트의 수 

 

세그멘테이션에 의한 주소변환

CPU가 논리 주소를 주면 두 부분 s, d로 나눈다. 세그먼트 번호 s와 오프셋 d이다. 

세그먼트 테이블의 시작 위치는 STBR이 알고 있다.

세그먼트 테이블에서 세그먼트 번호 s만큼 엔트리를 이동한다. 

그럼 테이블의 그 값이 세그먼트가 물리적인 메모리의 어떤 주소에 있는지 나타낸다.

세그멘테이션 기법은 페이징하고 다르게 엔트리에 2가지 정보를 갖고 있다.

limit이라는 세그먼트의 길이 정보도 갖고 있다.

페이징 기법에서는 페이지 길이가 다 동일해서 이 정보가 필요없었다.

반면 세그먼트는 길이가 일정하지 않아서 길이 정보도 알고 있어야 한다.

 

그래서 요청에 대해 조건을 검사해야 한다. 

1. 세그먼트 번호

논리주소의 세그먼트 번호 s가 STLR의 값(프로세스의 세그먼트 개수) 보다 작거나 같은지 확인한다.

더 큰 값을 요청하면 잘못된 요청이므로 trap이 발생시킨다.

2. d와 세그먼트 길이 비교 

세그먼트의 길이보다 offset d가 더 크면 잘못된 요청이므로 trap을 발생시킨다.

 

두가지 조건을 만족하면 주소변환을 한다. 세그먼트의 시작 위치에 offset을 더해서 주소변환을 한다. 

 

세그멘테이션의 단점은 

- first fit이나 best fit으로 메모리 공간을 할당해줘야 한다. 

- 세그먼트의 크기가 균일하지 않기 때문에 중간중간에 작은 hole이 생긴다. (외부 조각이 발생한다.) 

 

장점은 의미단위로 하는 일에 유리하다.

- Protection을 할 때 세그먼트별로 의미부여를 하면 자연스럽다. (code는 read only로 )

반면 페이지는 크기단위로 잘라서 의미단위 프로텍션이 애매하다. 페이지 안에 code랑 stack이 섞여있을수 있다.

- sharing도 효율적이다. 

의미단위로 쉐어링 하기 좋다. 페이징보다 유리하다. 

 

페이지는 프로그램 당 개수가 매우 많은 반면 세그멘트는 프로그램 하나에 개수가 많지 않다. 

따라서 테이블을 위한 메모리 낭비가 심한 쪽은 페이지이다. 

 

세그멘테이션 예시

 

위 예제는 하나의 프로그램을 구성하는 세그먼트가 5개인 상황이다. 

세그먼트 별로 크기가 다르다.

세그먼트 테이블에 세그먼트의 물리적인 메모리에서의 시작 주소와 길이 정보가 있다.

 

세그먼트 공유 

 

세그먼트 공유 예시

세그먼트를 서로 다른 2개의 프로세스가 공유하는 예시이다. 

0번 세그먼트(editor)는 code를 담고 있는 세그먼트이다. 

세그먼트를 공유하려면 프로세스 내에서 같은 논리적 주소를 가져야 한다. 프로세스1, 프로세스2에서 모두 0번 세그먼트이다. 

두 프로세스의 세그먼트 테이블을 보면 공유 세그먼트의 base, 즉 물리 메모리에서의 시작 주소가 같은 것을 확인할 수 있다. 즉 물리 메모리에는 하나의 세그먼트만 올리고 공유한다.

 

Segmentation + Paging

세그먼트와 페이징을 혼합한 기법이다.

세그먼트 하나가 여러개의 페이지로 구성된다.

따라서 먼저 세그먼트에 대한 주소 변환을 하게 된다.

논리주소는 s,d 즉 세그먼트 번호 s와 offset d로 구성된다.

세그먼트 테이블의 위치는 STBR에 들어 있다. 찾아서 s번째 엔트리로 가서 세그먼트에 대한 주소변환 정보를 찾는다.

 

혼합 방식에서는 세그먼트 하나가 여러개의 페이지로 구성된다. 메모리에 올라갈 때는 페이지로 쪼개져서 올라간다.

따라서 Allocation 문제가 발생하지 않는다.

대신 세그먼트 단위에서 하는게 유리한 protection, sharing은 세그먼트 단위로 한다. 세그먼트 테이블에 관련 정보 (read only 인지) 등을 놓는다. 

즉 두가지 방법의 장점을 모두 누릴 수 있다.

 

아무튼 이 기법에서는 세그멘테이션에 대해 주소변환을 하면 페이지 테이블의 시작 위치가 나온다. 

세그먼트 당 페이지 테이블이 존재한다. 

세그먼트에서의 offset d를 페이지 번호 p와 페이지 내에서 offset d'으로 자른다. 

페이지 테이블에서 p만큼 떨어진 엔트리로 가면 그 페이지의 주소변환 정보를 얻을 수 있다. 

물리적인 메모리의 몇번째 프레임인지 프레임 번호를 얻는다. 

따라서 프레임 번호 f를 얻으면 최종적으로 물리 주소 f d'이 된다. 

 

마치며

주소변환에 있어 운영체제의 역할은?

없다. 다 하드웨어가 하는 역할이다. 

프로세스가 CPU를 갖고 있으면서 메모리접근을 하는 것은 OS의 도움을 받지 않는다. 

도움을 받으려면 CPU가 OS에게 넘어가야 하는데 이건 말이 안된다. 

주소변환은 무조건 HW적으로 이루어지는 일이다.

 

운영체제가 끼어들어야 하는 일은 메모리접근이 아닌, IO 장치에 접근할 떄 이다.