[운영체제OS]7. 메모리 관리 -2(페이징 기법, 세그먼테이션)

********************************

##이 글은 제가 공부하고 있는 책을 요약해놓은 것이므로 본문 내용만 봐선 이해가 어려울 수 있습니다.

 

목차

4. 페이징 기법

5. 세그먼테이션

6. 페이지드 세그먼테이션

********************************

 

4. 페이징 기법

페이징(paging) 기법: 프로세스의 주소 공간을 동일한 크기의 페이지 단위로 나누어 물리적 메모리의 서로 다른 위치에 페이지들을 저장. 각 프로세스 주소 공간 전체를 메모리에 한꺼번에 올리지 않고 일부를 백킹스토어(스왑영역), 일부를 물리적 메모리에 혼재시키는 것이 가능. 물리적 메모리를 페이지와 동일한 크기의 프레임(frame)으로 미리 나누어둠. 빈 프레임이 있으면 어느 위치든 사용될 수 있기때문에 페이징 기법에서는 연속할당에서 발생했던 동적 메모리 할당 문제가 발생하지 않는다는 장점을 가짐. 페이징 기법은 주소 변환 절차가 연속할당 방식에 비해 다소 복잡. 하나의 프로세스라 해도 페이지마다 물리적 메모리에 올리는 위치가 제각각이기에, 논리적 주소를 물리적 주소로 변환하는 작업이 페이지 단위로 이루어져야 함. 이를 위해 페이징 기법에선 페이지 테이블(page table)을 가지며, 프로세스가 가질 수 있는 페이지 수만큼의 주소 변환 엔트리를 가짐. 페이징 기법에선 외부조각(가용 공간 크기가 작아서 빈 공간임에도 활용되지 못하는 부분)이 발생하지 않지만, 프로그램의 크기가 항상 페이지 크기의 배수가 되진 않기때문에 프로세스의 주소 공간 중 제일 마지막에 위치한 페이지에서는 내부조각이 발생할 수 있음.

 

1) 주소 변환 기법

CPU가 사용하는 논리적 주소를 페이지 번호(p)와 페이지 오프셋(d)으로 나누어 주소변환에 사용. 페이지 번호는 각 페이지별 주소 변환 정보를 담고 있는 페이지 테이블 접근 인덱스로 사용되고, 해당 인덱스의 항목에는 그 페이지의 물리적 메모리상의 기준 주소가 저장됨. 따라서 특정 프로세스의 p번째 페이지가 위치한 물리적 메모리의 시작 위치는 페이지 테이블의 p번째 항목을 보면 됨. 페이지 오프셋은 하나의 페이지 내에서의 변위를 알려줌. 기준 주소값에 변위를 더함으로써 요청된 논리적 주소에 대응하는 물리적 주소를 얻음.

 

2) 페이지 테이블 구현

페이지 테이블은 주소 변환을 위한 자료구조로, 물리적 메모리에 위치함. 프로세스의 페이지 테이블에 접근하기 위해 운영체제는 2개의 레지스터를 사용. 페이지 테이블 기준 레지스터(page-table base register)는 메모리 내에서의 페이지 테이블의 시작 위치를 가리킴, 페이지 테이블 길이 레지스터(page-table length register)는 페이지 테이블의 크기를 보관. 

페이징 기법에서 메모리 접근 연산은 총 2번일어남(주소변환을 위해 페이지테이블에 접근, 변환된 주소에서 실제 데이터에 접근). 따라서 두번의 메모리 접근을 필요로 하고 이에 따른 오버헤드가 발생. 이와 같은 오버헤드를 줄이고 메모리의 접근 속도를 향상시키기 위해 TLB(Translation Look-aside Buffer)라고 불리는 고속의 주소 변환용 하드웨어 캐시를 사용.

TLB로 사용되는 하드웨어는 가격이 비싸 빈번히 참조되는 페이지에 대한 주소 변환 정보만 담음. 따라서 요청 페이지에 대한 주소 변환 정보가 TLB에 존재할수도, 아닐 수도 있음. 존재한다면 곧바로 물리적 메모리의 프레임 번호를 얻을 수 있지만, 존재하지 않는 경우 메인 메모리에 있는 페이지 테이블로부터 프레임 번호를 알아내야 한다. 

한편 페이지 테이블과 TLB에 저장되어 있는 정보는 그 형태가 조금 다름. 페이지 테이블은 페이지 번호가 주어지면 테이블의 시작 위치에서 페이지 번호만큼 떨어진 항목에 접근해 해당 페이지에 대응하는 프레임 번호를 얻을 수 있다. 반면 TLB를 사용한 주소 변환의 경우 모든 페이지에 대한 주소 변환 정보를 갖고있는 것이 아니라서 페이지 번호와 이에 대응하는 프레임 번호가 쌍으로 저장되어야 한다. 또한 해당 페이지에 대한 주소 변환 정보가 TLB에 있는지 확인하기 위해 모든 항목을 찾아봐야 하는 오버헤드가 발생한다. 이 오버헤드를 줄이기 위해 TLB 구현에는 병렬탐색(parallel search)이 가능한 연관 레지스터(associative resister)를 사용한다. 병렬탐색은 TLB 내의 모든 항목을 동시에 탐색하는 기능. 한번의 TLB 접근 시간으로 TLB에 주소 변환 정보가 있는지 확인. 연관 레지스터를 사용할 때 평균적인 메모리 접근시간(Effective Access Time:EAT)을 알아보자. 메모리에 접근하는 시간을 1, 연관 레지스터에 접근하는 시간 e, 요청 페이지에 대한 주소변환 정보가 연관 레지스터에 존재할 확률을 a라 하면 EAT는 다음과 같다. EAT=(1+e)a + (2+e)(1-a)=2+e-a

TLB에 주소변환 정보가 존재하는 경우 실제 데이터에 접근하기 위해 한번의 메모리 접근이 필요해서 1+e시간이 필요하고 TLB에 주소변환 정보가 없을 경우 페이지테이블에 접근하는 시간이 더해져 총 2번의 메모리 접근이 필요해서 2+e시간이 필요.

 

3) 계층적 페이징

32비트 주소 체계의 컴퓨터는 2^32byte(=4GB)의 주소공간을 갖는 프로그램을 지원할 수 있다. 페이지 크기가 4KB라면 4GB/4KB, 즉 1M개의 페이지 테이블 항목이 필요하게 된다. 컴퓨터 시스템에서는 K=2^10, M=2^20, G=2^30로 정의됨. 각 페이지 테이블 항목이 4byte씩을 필요로 한다면 한 프로세스당 페이지 테이블을 위해 1M*4byte=4MB가 필요. 수행 중인 프로세스 수가 증가함에 따라 전체 메모리의 상당부분이 주소 변환을 위한 페이지 테이블에 할애되어 실제로 사용 가능한 메모리 공간의 낭비가 심해진다. 이 낭비를 줄이귀 위해 2단계 페이징(two-level paging) 기법을 사용.

2단계 페이징 기법에서는 주소 변환을 위해 외부 페이지 테이블(outer page table)과 내부 페이지 테이블(inner page table)의 두 단계에 걸친 페이지 테이블을 사용. 사용하지 않는 주소 공간에 대해서 외부 페이지 테이블 항목을 NULL로 설정하며, 여기에 대응하는 내부 페이지 테이블을 생성하지 않는 것이다. 이런 식으로 낭비를 줄일 수 있다. 즉 페이지 테이블을 위해 사용되는 메모리 공간을 줄여 공간적인 이득을 볼 수 있다. 하지만 주소 변환을 위해 접근하는 페이지 테이블 수가 증가하므로 시간적인 손해가 따른다.

2단계 페이징 기법에선 프로세스의 논리적 주소를 두 종류의 페이지 번호(P1, P2)와 페이지 오프셋(d)로 구분. 첫번째 페이지 번호 P1은 외부 페이지 테이블 인덱스, 두번째 페이지 번호 P2는 내부 페이지 테이블 인덱스. 논리적 주소를 <P1, P2, d>와 같은 형태로 표시하면, 외부 페이지 테이블로부터 p1만큼 떨어진 위치에서 내부 페이지 테이블의 주소를 얻고, 거기서 다시 p2만큼 떨어진 위치에서 요청된 페이지가 존재하는 프레임의 위치를 얻고, 그 프레임으로부터 d만큼 떨어진 곳에서 원하는 정보에 접근할 수 있게 됨. 

32비트 주소체계를 갖는 시스템에서 페이지 하나의 크기를 4KB, 페이지 테이블 항목의 크기를 4byte라고 하자. 페이지 크기가 4KB(=2^12byte)이므로 하나의 페이지 내에서의 바이트 오프셋을 결정하기 위해 12비트 필요. 따라서 총 32비트중 최하위 12비트가 오프셋 d로 사용됨. 한편 2단계 페이징 기법에선 내부 페이지 테이블 자체를 하나의 프레임에 보관함. 즉 4KB 페이지를 사용하는 이 예제의 경우 내부 페이지 테이블의 크기 역시 4KB가 된다. 페이지 테이블 항목의 크기가 4byte이므로 내부 페이지 테이블은 4KB/4byte=1K개의 항목을 가짐. 이들 2^10개를 구분하기 위해 10비트가 필요. 따라서 인덱스 P2에는 10비트가 할당되어야 함. 끝으로 외부 페이지 테이블의 인덱스인 P1에는 32비트중 나머지 10비트가 할당됨. 

프로세스 주소 공간이 커질수록 페이지 테이블의 크기도 커지므로 주소 변환을 위한 메모리 공간 낭비가 더 심해진다. 이럴 경우 3단계, 4단계와 같은 다단계 페이지 테이블이 필요하게 됨. 이는 메모리 공간의 소모는 줄일 수 있지만 그만큼 메모리에 대한 접근 횟수가 많아지므로 메모리 접근시간이 크게 늘어나는 문제가 발생. 따라서 시간적 오버헤드를 줄이기 위해서는 TLB를 사용하는 것이 효과적. TLB를 함께 사용하면 공간적 이득을 얻음과 동시에 메모리 접근 시간도 그닥 늘어나지 않아 시간적 효율성도 얻게 됨.

메모리 접근시간 100ns, TLB 접근시간 20ns, 요청된 페이지에 대한 주소 변환 정보가 TLB에 있을 확률 98%, 4단계 페이지 테이블을 사용하는 경우일때 평균적인 메모리 접근시간(EAT)는 EAT= 0.98*(100+20) + 0.02*(100*5+20) = 128ns가 됨. 

 

* 2단계 페이징 기법은 따로 글을 썼습니다.

https://yiyj1030.tistory.com/501?category=462811 

[운영체제] 2단계 페이징 테이블 기법 알아보기

 

4) 역페이지 테이블

페이지 테이블로 인한 메모리 공간의 낭비가 심한 이유는 모든 프로세스의 모든 페이지에 대해 페이지 테이블 항목을 다 구성해야 하기 때문. 이 대안으로 역페이지 테이블(inverted page table) 기법이 사용될 수 있음. 논리적 주소에 대해 페이지 테이블을 만들지 않고 물리적 주소에 대해 페이지 테이블을 만드는 것. 즉 각 프로세스마다 페이지 테이블을 두지 않고, 시스템 전체에 페이지 테이블을 하나만 두는 방법. 페이지 테이블의 각 항목은 프로세스 번호(pid)와 그 프로세스내의 논리적 페이지 번호(P)를 담고 있게 됨. 주소 변환 작업이 논리적 주소로부터 물리적 주소를 얻어내는 것과는 반대로 역페이지 테이블은 물리적 주소로부터 논리적 주소를 얻기 쉬운 구조라서 역페이지 테이블에서의 주소 변환은 다소 비효율적인 측면이 있음. 역페이지 테이블에 주소 변환 요청이 들어오면 그 주소를 담은 페이지가 물리적 메모리에 존재하는지 여부를 판단하기 위해 페이지 테이블 전체를 다 탐색해야 하는 어려움이 있다. 이는 상당한 시간이 소요되서 역페이지 테이블은 일반적으로 메모리를 유지하는 대신 연관 레지스터에 보관해 테이블 전체 항목에 대한 병렬탐색을 가능하게 함으로써 시간적 효율성을 꾀하게 됨. 

역페이지 테이블은 f값을 알면 pid, p를 얻기 쉬운 구조로 되어있다. 즉 물리적 주소를 알면 논리적 주소를 쉽게 알아낼 수 있도록 설계되어 있다.

 

5) 공유 페이지

공유코드(shared code): 여러 프로세스에 의해 공통으로 사용될 수 있도록 작성된 코드를 말하며 재진입 가능 코드 또는 순수 코드라고도 불리며 읽기전용(read-only)의 특성을 갖고 있음. 공유 페이지(shared page)란 공유 코드를 담고 있는 페이지를 말함. 여러 프로세스에 의해 공유되는 페이지이므로 물리적 메모리에 하나만 적재되어 메모리를 좀 더 효율적으로 사용할 수 있게 됨. 공유 코드는 읽기전용의 성질을 가져야 하고, 모든 프로세스의 논리적 주소 공간에서 동일한 위치에 존재해야 하는 제약이 있음. 즉 공유페이지는 그 페이지를 공유하는 모든 프로세스의 주소 공간에서 동일한 페이지 번호를 가져야 한다. 예를 들어 문서 편집기 프로그램의 코드가 코드1, 코드2, 코드3의 세 페이지로 구성되고, 이 페이지들이 프로세스 P1, P2, P3에 의해 공유된다면 코드1, 2, 3 페이지는 세 프로세스의 주소 공간 내에서 동일한 위치에 존재해야 하며, 물리적 메모리에는 하나씩의 코드만이 올라가게 된다.

6) 메모리 보호

페이지 테이블의 각 항목에는 주소 변환 정보뿐 아니라 메모리 보호를 위한 보호비트(protection bit)와 유효-무효 비트(valid-invalid bit)를 두고 있다. 보호비트는 각 페이지에 대한 접근 권한의 내용을 담고 있음. 각 페이지에 대해 어떠한 접근을 허용하는지의 정보가 보호비트에 저장됨. 즉 보호비트는 각 페이지에 대해 읽기-쓰기/읽기전용 등의 접근 권한을 설정하는 데에 사용. 유효-무효 비트는 해당 페이지 내용이 유효한지에 대한 내용을 담음. 비트가 유효로 세팅되어 있으면 해당 메모리 프레임에 그 페이지가 존재함을 뜻하며 접근이 허용됨. 반면 무효면 프로세스가 그 주소부분을 사용하지 않거나, 해당 페이지가 물리적 메모리에 올라와 있지 않고 백킹스토어에 존재해 해당 메모리 프레임에 유효한 접근 권한이 없다는 의미.

 

 

5. 세그먼테이션

세그먼트(segment)는 주소 공간을 기능 단위 또는 의미 단위로 나눈 것. 일반적으로 코드, 데이터, 스택 등의 기능 단위로 세그먼트를 정의. 따라서 세그먼트는 페이지와 달리 크기가 균일하지 않다. 그래서 크기가 다른 세그먼트들을 메모리에 적재하는 부가적인 관리 오버헤드가 뒤따르게 된다. 세그먼테이션 기법에선 논리적 주소가 <세그먼트 번호, 오프셋>으로 나뉘어 사용됨. 세그번트 번호는 해당 논리적 주소가 주소 공간 내 몇번째 세그먼트인지 나타내고, 오프셋은 그 세그먼트 내에서 얼만큼 떨어져 있는지에 대한 정보. 세그먼테이션 기법에선 주소 변환을 위해 세그먼트 테이블을 사용한다. 세그먼트 테이블의 각 항목은 기준점(base)와 한계점(limit)을 가지고 있다. 기준점은 물리적 메모리에서 그 세그먼트의 시작 위치를, 한계점은 그 세그먼트의 길이를 나타냄.  페이징 기법에선 페이지 크기가 동일해서 페이지 테이블의 항목에 기준점이라 할 수 있는 페이지 프레임 위치만 유지하고 있으면 되지만, 세그먼테이션 기법에선 세그먼트 크기가 균일하지 않으므로 세그먼트 위치 정보뿐만 아니라 길이 정보를 함꼐 보관하는 것이다. 

페이징 기법에서 주소 변환 시 페이지 테이블 기준 레지스터(PTBR)와 페이지 테이블 길이 레지스터(PTLR)의 도움을 받았듯이, 세그먼테이션 기법에서도 세그먼트 테이블 기준 레지스터(STBR)와 세그먼트 테이블 길이 레지스터(STLR)을 사용. 

STBR은 실행중인 프로세스의 세그먼트 테이블이 메모리의 어느 위치에 있는지 그 시작 주소를 담고 있고, STLR은 그 프로세스의 주소 공간이 총 몇 개의 세그먼트로 구성되는지, 즉 세그먼트 개수를 나타냄. 

세그먼테이션 기법에선 논리적주소를 물리적 주소로 변환하기 전에 두가지 사항을 먼저 확인함. 첫번째는 요청된 세그먼트 번호가 STLR에 저장된 값보다 작은지 확인. 그렇지않으면 존재하지 않는 세그먼트에 대한 접근 시도이므로 예외상황을 발생시킴. 두번째는 논리적 주소의 오프셋값이 그 세그먼트의 길이보다 작은지 확인. 이는 세그먼트 테이블의 해당 항목에 있는 한계점과 요청된 논리적 주소의 오프셋값을 비교하여 확인함. 그렇지 않다면 역시 예외상황을 발생시킴.

페이징 기법과 마찬가지로 보호비트와 유효비트를 가짐. 보호비트는 각 세그먼트에 대해 읽기/쓰기/실행 등의 권한이 있는지를 나타내며, 유효비트는 각 세그먼트의 주소 변환 정보가 유효한지, 즉 해당 세그먼트가 현재 물리적 메모리에 적재되어 있는지를 나타낸다. 세그먼테이션 기법에서도 공유 세그먼트 개념을 지원하며, 공유 세그먼트는 이 세그먼트를 공유하는 모든 프로세스의 주소 공간에서 동일한 논리적 주소에 위치해야 한다. 

세그먼트는 의미 단위로 나누어져 있기때문에 공유와 보안 측면에서 효과적. 페이징 기법에서는 동일한 크기로 주소 공간을 나누다 보면 공유하려는 코드와 사유 데이터 영역이 동일 페이지에 공존하는 경우가 발생할 수 있다. 세그먼테이션기법에서는 이러한 현상이 발생하지 않으므로 공유나 보안처럼 의미있는 단위에 대해 수행하는 업무에선 장점을 가짐. 

한편 세그먼트의 길이가 균일하지 않아 외부조각이 발생하게 되며, 세그먼트를 어느 가용공간에 할당할 것인지 결정하는 문제가 발생. 이는 연속할당 메모리 관리의 가변분할 방식에서의 문제와 동일한 범주의 문제. 할당 방식에는 해당 세그먼트 크기보다 크거나 같은 첫번째 가용 공간에 할당하는 최초적합(first fit) 방식과 세그먼트 크기보다 크거나 같은 가용 공간 중 가장 작은 공간에 할당하는 최적적합(best fit) 방식이 있다. 

 

 

6. 페이지드 세그먼테이션

페이지드 세그먼테이션은 페이징 기법과 세그먼테이션 기법의 장점만을 취한 주소 변환 기법. 세그먼테이션 기법과 마찬가지로 프로그램을 의미 단위의 세그먼트로 나누지만 세그먼트가 임의의 길이를 가지지 않고 동일한 크기의 페이지들의 집합으로 구성되어야 한다. 물리적 메모리에 적재하는 단위는 페이지 단위다. 즉 세그먼트의 크기를 페이지 크기의 배수가 되도록 하여 세그먼테이션 기법에서 발생하는 외부조각의 문제점을 해결하며, 세그먼트 단위로 프로세스 간의 공유나 프로세스 내의 접근 권한 보호가 이루어지도록 함으로써 페이징 기법의 약점을 해소. 

주소변환을 위해 외부의 세그먼트 테이블과 내부의 페이지 테이블, 이렇게 두 단계의 테이블을 이용. 하나의 세그먼트가 여러 개의 페이지로 구성되므로 각 세그먼트마다 페이지 테이블을 가지게 됨.

<세그먼트 번호, 오프셋>으로 구성된 논리적 주소를 물리적 주소로 변환하는 과정은 다음과 같음. 논리적 주소의 상위 비트인 세그먼트 번호를 통해 세그먼트 테이블의 해당 항목에 접근. 이 세그먼트 항목에는 세그먼트 길이와 세그먼트 페이지 테이블 시작 주소가 들어있다. 이때 세그먼트 길이값과 논리적 주소 중 하위 비트인 오프셋값을 비교하여 메모리 접근이 가능한지 체크, 오프셋이 더 크다면 트랩을 발생시키고 그렇지 않다면 오프셋을 다시 상위와 하위 비트로 나누어 상위 비트는 세그먼트 내에서의 페이지 번호로 사용하고 하위 비트는 페이지 내에서의 변위로 사용. 세그먼트 테이블의 항목을 통해 해당 세그먼트를 위한 페이지 테이블의 시작 위치를 얻었으므로 그 위치에서 페이지 번호만큼 떨어진 페이지 테이블 항목으로부터 물리적 메모리의 페이지 프레임 위치를 얻게 됨. 이 위치에서 오프셋의 하위 비트값인 페이지 내 변위만큼 떨어진 곳이 원하는 물리적 메모리 주소가 됨.