[Memory Management, 메모리 할당 방식 [운영체제] 에 이어서
불연속 할당에 대해서 알아보자
그 중 가장 대표적인 페이징에 대해서 알아보자
Paging 기법은 앞서 설명했던 것처럼 해당 프로세스의 관련된 데이터 모두를 적재하는 것이 아니다.
단순히 레지스터에 시작주소 값을 담아 사용하기에는 연속된 메모리영역이 필요하다.
이제 프로세스의 물리 주소 공간이 연속되지 않아도 되는 메모리 관리 기법인 페이징을 쓰는 것이다.
페이징은 연속 메모리 할당을 괴롭히는 2가지 문제인
외부 단편화, 관련 압축의 필요성을 피할 수 있게 한다.
이러한 많은 이점을 제공하기 때문에
대형 서버용 시스템부터 모바일 장치용 시스템까지 대부분의 운영체제에서 다향한 형태의 페이징이 사용된다.
++페이징은 운영체제와 컴퓨터 하드웨어 간의 협력을 통해 구현된다.
물리 메모리는 프레임(frame)이라 불리는 같은 크기 블록으로 나누어진다.
논리 메모리는 페이지(page)라 불리는 같은 크기 블록으로 나누어진다.
++ page size는 하드웨어에 의해 결정된다.
**페이징 기법을 사용하면 외부 단편화가 발생하지 않는다.
// 모든 놀고 있는 프레임이 프로세스에 할당가능하기 때문이다.
그렇지만 내부 단편화가 발생한다.
할당은 항상 프레임의 정수배로 할당되기 때문에 프로세스가 페이지 경계와 일치하지 않는 크기의 메모리를 요구한다면, 마지막 페이지 프레임은 전부 할당되지 않는다.
// 4칸 중 3칸만 채워지고 1칸 남을수도 있겠지?
근데 이게 또 딜레마인게
프레임 모두 할당한답시고 페이지 크기를 무진장 작게 만들면 페이지 테이블의 크기가 커지게 되고 페이지 테이블이 차지하는 공간이 낭비된다.
그렇다고 엄청 크게 만들면 2049B인데 2048B의 페이지의 크기를 가지면 2번째 페이지가 1칸 빼고 다 낭비되는 불상사도 생긴다.
아래 그림을 보자
논리적 page로 자르고 실제 물리적 frame이 비어있다면 어디든 적재할 수 있게 만든 것이다.
해당 과정에서는 MMU와 같이 논리적 주소를 물리적 주소에 매핑해주는 작업이 필요한데
이를 page table이 물리적 주소에 대한 정보를 담고있어서 참조를 도와준다.
**page table은 논리적 page의 개수만큼 entry가 존재한다.
• Page number (p) – used as an index into a page table which contains base address of each page in physical memory
• Page offset (d) – combined with base address to define the physical memory address that is sent to the memory unit
**CPU에서 나오는 모든 주소는 페이지 번호와 페이지 오프셋 부분으로 나누어진다.
page number는 프로세스 페이지 테이블(page table)에 접근할 때 사용된다.
page table은 물리 메모리의 각 프레임의 시작 주소를 저장하고 있다.
page offset은 참조되는 프레임(물리적 메모리) 안에서의 위치다.
page0이 한국을 가리킨다면 page0의 offset은 각종 대도시 서울, 부산을 가리킬 수 있는 값이 되는 것이다.
따라서, 프레임의 시작 주소와 페이지 오프셋이 결합해서 물리 메모리 주소가 된다.
페이지 테이블 = 페이지 번호(물리메모리 시작주소) + 페이지 오프셋(프레임 안에서 위치)
//프로그램 카운터의 원리랑 비슷하다.
어떻게 물리적 주소로 바꾸냐..?
1. 페이지 번호를 추출하여 페이지 테이블의 인덱스로 사용
2. 페이지 테이블에서 해당 프레임 번호 추출
3. 논리 주소의 페이지 번호를 프레임 번호로 바꿈
**오프셋은 변하지 않기 때문에 바꾸지 않아도 되고 프레임 번호와 오프셋은 이제 물리 주소를 가리킨다.
결국
즉, CPU에서 논리적 주소를 이용하여 연산을 시도하면
page number에 맞는 page table을 참고하여 물리적 주소를 만들어내고
offset을 이용하여 해당 주소로 물리적 메모리에 접근할 수 있다.
도대체 물리적 주소를 어떻게 정하는 걸까?
일반적으로 페이지 크기는 2^n 이고 일반적으로 4KB~~1GB사이의 크기를 가진다.
페이지 크기로 2의 거듭제곱을 선택하면 논리 주소를 페이지 번호 및 페이지 오프셋으로 쉽게 변환할 수 있다.
논리 주소 공간의 크기가 2^m, 페이지 크기가 2^n 바이트라고 하자.
논리 주소의 상위 m-n 비트는 페이지 번호, n하위 비트는 페이지 오프셋
즉, p는 페이지 테이블의 인덱스, d는 페이지 내에서 오프셋으로 사용된다.
예를 들면
n= 2 ,m =4라고 볼 수 있다.
4 B의 페이지 크기와 32B의 물리 메모리가 있다.
논리주소 0은 페이지 0, 오프셋 0이다.
페이지 테이블을 색인으로 찾아서 페이지 0이 프레임 5에 있다는 것을 알아낸다.
페이지는 프레임 5에 있고 // 4개의 논리주소들은??
그 안에있는 논리 주소 0은 실제주소 20[=(5*4) + 0]으로 사상(mapping)된다. //a를 말한다
.....
.....
논리주소 3은(페이지 0 오프셋 3) 은 실제주소 23[=(5*4) + 3]으로 사상(mapping)된다. //d를 말한다.
페이지가 사용자에게 주는 이점
페이지는 우리에게 물리적 메모리와의 인터페이스를 제공한다고 생각할 수도 있다.
우리는 페이지만 신경을 써주면 된다.
실제 물리적 메모리에 연속적으로 접근이 되든 안되든 우리는
논리적주소를 연속적으로 쓴다.
일반적으로 한 프로세스가 실행되기 위해 도착하면 그 프로세스의 크기가 페이지 몇 개 분에 해당하는가를 조사한다.
각 사용자 페이지는 한 프레임씩 필요하다.
다시, 프로세스가 n개의 페이지를 요구하면 메모리에서 이용할 수 있는 프레임이 n개 있어야 한다는 말이다.
n개의 프레임을 사용할 수 있다면 이 프레임들은 이 프로세스에 할당한다.
그러고는 프로세스의 처음 페이지가 할당된 프레임 중 하나에 적재되고
그 프레임 번호가 페이지 테이블에 기록된다.
그 다음 페이지는 또 다른 프레임에 적재되고, 또 그 프레임 번호가 페이지 테이블에 기록되며 반복된다.
페이징의 가장 중요한 특징은 메모리에 대한 프로그래머의 인식과 실제 내용이 서로 다르다는 것이다.
프로그래머는 메모리가 하나의 연속적인 공간이며, 메모리에는 이 프로그램만 있다고 착각한다.
실제로는 프로그램은 여러 곳에 프레임 단위로 분산되어 있고, 많은 프로그램이 올라와 있다.
**그러니까 프로그래머는 물리 메모리에 프로그램이 올라있다고 생각한다.
이 차이는 주소 변환 하드웨어에 의해 메워진다.
//논리 주소는 물리 주소로 변환된다.
운영체제는 물리 메모리를 관리하기 때문에 물리 메모리의 자세한 할당에 대해 파악하고 있어야 한다.
즉, 어느 프레임이 할당되어 있고, 어느 프레임이 사용 가능한지, 총 프레임은 몇 개나 되는지 등을 알아야 한다.
이런 정보는 일반적으로 프레임 테이블(frame table)이라는 시스템에 하나밖에 없는 자료구조에 있다.
그리고 운영체제는 모든 프로세스들의 주소들을 실제 주소로도 사상(mapping)할 수 있어야 한다.
만약 사용자가 system call 을 호츌하여 인자로 어떤 주소를 주면 제대로 사상하여 정확히 그 물리 주소를 찾아가야 한다.
운영체제는 명령 카운터와 레지스터의 사본을 유지하는 것처럼 각 프로세스의 페이지 테이블 사본을 유지한다.
이 사본은 운영체제가 논리 주소에 대응하는 물리 주소를 직접 사상해야 할 때마다 논리 주소를 물리 주소로 변환하는데 사용 한다.
또한 프로세스가 CPU에 할당될 때 CPU 디스패처가 하드웨어 디스패처 테이블을 설정하는 데 사용된다.
++ 페이징은 문맥 교환시간을 늘린다.
그렇다면 page table에는 어떻게 접근을 할까?
page table은 Main Memory에 있는데 레지스터로 하면 더 빠를 것 같지만
레지스터 가지기엔 용량이 너무 커서 그렇다.
어?? 근데 메인 메모리에 접근하려면 page table을 이용해야하는데
page table이 메인메모리에 있으면 어떻게 이용하냐????
그래서 page table의 위치와 page table의 크기는 레지스터가 가지도록 한다.
위에서 PTBR, PTLR이 그 역할을 수행한다.
메모리에 페이지 테이블을 저장하면 문맥 교환 속도가 빨라지지만 메모리 액세스 시간이 느려질 수 있다.
다시 말해서 메모리에 접근하기 위에 page table에 접근하고
다시 메모리에 접근하는 2번의 access가 필요해진다.
1. 메모리 i에 접근하려고 한다고 가정하자.
먼저 페이지 번호를 기준으로 PTBR 오프셋 값을 사용하여 페이지 테이블의 항목을 찾는다 이 작업에는 한 번의 메모리 접근이 필요하다.
2. 이렇게 얻은 프레임 번호와 페이지 오프셋을 결합하여 실제 주소를 생성한다.
그런 다음 메모리에서 원하는 위치에 액세스 할 수 있다.
( 1번은 페이지 테이블 항목, 다른 한번은 실제 데이터)
그래서 속도 향상을 위해 TLB, Translation Look-aside Buffer 라는 버퍼를 만들어냈다.
CPU와 Main Memory 사이에 존재하고
해당 버퍼는 캐시역할을 하며 최근에 접근한 page에 대한 물리적 주소를 저장해놓는다. (물론 일부만 저장)
** 캐시 역할을 한다.
page table을 접근하기 전에 TLB에 먼저 접근하고 miss가 나오면 그제서야 page table에 접근하게 된다.
하지만 해당 캐시에 접근할 때는
page table에 page number만 참조하면 되는 random access가 아니라 실제로 해당 페이지가 TLB에 들어있는지를 찾아야해서 너무 크게 만들어도 오버헤드가 높아지는 현상이 발생한다.
그래서 또 탐색이 빨라지는 기능을 넣었다.
때문에 TLB를 탐색할 때
Associative Register를 통해 병렬 탐색을 할 수 있게 한다.
최대한 오버헤드를 줄이는 것이다.
TLB에 페이지를 찾아달라고 요청이 들어오면 찾고 싶은 페이지를 동시에 여러 개의 내부 키(페이지 번호)와 비교한다.
페이지 번호가 같은 것을 찾으면 그에 대응하는 프레임 번호를 알려준다. // 검색도 빠르고 손실이 거의 없다
그리고 해당 TLB는 해당 프로세스에 의존적이므로 해당 프로세스가 아닐 때는 flush를 하고 다시 사용해야 한다.
context switch가 일어날 때, CPU 점유 프로세스가 달라질 때 초기화 후 사용해야 한다.
참고로
실제 접근 시간은 위와 같이 계산한다.
Hit ratio는 TLB에서 발견될 확률(hit rate)를 의미한다.
페이징을 응용해서 아래와 같은 구조를 만들었다.
아래는 2 단계 페이징을 말한다.
근데 굳이 페이지를 2개 만들어서 2번 접근하게 만드는 것이 효율적일까??
한 번 생각해보자.
현재에 와서는 매우 큰 프로그램이 등장했다.
Virtual Memory의 주소는 32bit 로 써서 4GB 까지 표현가능하다.
4GB를 일반적인 페이지 size인 4KB로 쪼갠다면 1MB 만큼의 page table entry가 필요하게 된다.
page table도 메인 메모리에 존재해야하고 각 프로그램마다 page table도 다를텐데
프로그램마다 4MB의 공간을 사용하게 된다.
실제 페이지는 프로그램 실행에 그렇게 많은 페이지가 쓰이지도 않는데 이는 심각한 메모리 낭비가 된다.
때문에 메모리, 공간적인 이유로 2 계층으로 페이지를 쓰겠다는 것이다.
아니 근데 page table 을 2개 쓰면 더 손해아니야??
사실 우리가 프로그램 실행 중에서 사용되는 페이지는 별로 안된다.
하지만 페이지 테이블의 엔트리는 모든 페이지 넘버에 대해서 만들어야 한다.
사용되지 않는 주소에 대해서 엔트리 값의 NULL이 되기 때문에 2단계를 하는 것이 더 효율적이다.
그렇게 되면 페이지를 통해 물리적인 메모리에 접근하는 방법도 약간 달라진다.
아래와 같이 조금 더 세분화된 작업이 필요하다.
때문에 32 bit에서
page number를 다시 나누어서 사용하게 된다.
일단 페이지의 크기가 4KB라고 하자.
4KB 는 2^12 B가 되며 때문에 페이지 내부에서 어떤 위치일지 결정하는 offset은 12bit가 된다.
그렇다면 outer page 와 page는 어떻게 할까?
결국 page table도 비슷하다.
아래 그림을 보자
페이지는 4KB라고 했다.
하지만 page table 자체가 page로 구성되게 된다.
또한 page table entry 가 4B이기 때문게
4KB/ 4B는 1K가 된다. 즉, 2^10개로 구분할 수 있게 된다.
위의 그림처럼 페이지가 구성이 된다.
위처럼 logical address가 구현이 된다.
그렇지만 64비트 논리 주소 공간을 가진 시스템에서는 2단계 페이징에서도 별로다.
별로인 이유를 예를 들어서 설명해보겠다.
페이지 크기가 4KB라고 가정하자(2^12) 이 경우 페이지 테이블은 2^52가 될 것이다.
2단계 페이징 기법을 사용한다면?
이렇게 나눠질 것이다.
바깥쪽 테이블이 너무 커진다.. 그래서 2레벨이 아닌 3레벨 페이징을 하기도 하는데
너무 비효율적이다. 그래서 우리는 다른 방법을 찾아보기로 했다.
실제로 2단계 이상의 계층을 가지게 된다면
page table을 위한 공간을 줄일 수는 있다. 그렇다면 시간적으로 손해가 아닐까?? 생각하게 되지만
아래와 같이 메모리에 대해서 접근 시간을 TLB를 통해 줄일 수 있다면
생각보단 그렇게 오버헤드가 크지 않은 것을 알 수가 있다.
페이징 환경에서 Data Protection, 데이터 보호는 어떻게 될까??
즉, page table에서 해당 프로세스가 사용하지 않는 페이지, frame에 접근하려고 하면 어떻게 할까?
(위에서도 page 는 일부만 쓰이기 떄문에 page table의 크기를 줄이고자 page table을 multi-level로 쓴 것이다)
각 페이지마다 보호 비트(protection bits)라는게 있는데 이것들에 의해서 보호가 된다.
(read/write/read-only)
또한 다른 bit 도 존재한다.
page table엔 사실 frame(물리적 주소) 뿐만이 valid bit라는 부가적인 정보가 들어있다.
각 비트는 이 페이지가 읽기 또는 쓰기가 허용되었는지를 알려준다.
메모리 접근은 페이지 테이블을 거치므로 주소 변환과 함께 페이지가 허용된 것이 무엇인지 같이 전달받는다.
++0 이면 무효, 1이면 유효
이 비트가 유효하면 페이지가 프로세스의 합법적인 페이지임을 나타낸다.
무효로 설정되면 그 페이지는 프로세스의 논리 주소 공간에 속하지 않는다는 것을 나타낸다.
접근 할 경우 trap 발생
// 이 비트를 이용해서 페이지에 대한 접근 허용 여부를 결정한다.
즉, 여기서 페이지 6,7 에서 주소를 매핑하려고 시도하면, 비트가 invalid이기 때문에 trap을 발생시킨다.
**프로세스가 자신의 모든 주소 범위를 늘 사용하는 경우는 드물다.
그래서 프로세스들은 일정한 시각에는 일부분만을 집중적으로 사용한다.
이 경우 모든 페이지에 페이티 테이블 항목을 배정하는 것은 낭비다.
그래서 몇몇은 "페이지 테이블 길이 레지스터, PTLR" 를 이용해서 프로세스가 제시한 주소가 유효한 범위 내에 있는지를 확인하기 위해 모든 논리 주소 값이 PTLR(page table length register) 와 비교한다.
page table이 커서 나온 구조 중에
Inverted Page Table Architecture 라는 것도 있다.
바로 아래와 같은 구조이다.
원래는 프로세스마다 page table이 따로 존재했지만
이 구조에서는 page table이 유일하게 존재한다.
즉, page table의 entry가 process의 페이지 개수만큼 존재하는 것이 아니라 물리적 메모리의 frame의 개수만큼 존재하는 것이다.
원래의 page table에는 page 번호의 순서대로 배열되어있었지만
frame의 순서대로 되어있다.
즉, page table의 논리적 주소는 첫번째 frame을 가리키는 것부터 순서대로 되어있다는 말이다.
딱히 깊게 알아야 할 필요는 없다.
그냥 알고 넘어가면 된다.
때로는 페이지도 공유해서 읽을 수가 있다.
Shared Page라고 한다.
예를 들어
메모장을 여러 개 켜놓는다고 가정하자.
메모장의 사용방법은 동일할 것이다
무엇을 쓰느냐만 달라질 뿐
즉, 코드가 공유해서 실행이 가능하다면
메모리에 하나만 올려도 된다는 것이다.
올릴 때 read-only로 코드가 바뀌어 에러가 생기는 것을 방지한다.
다른 내용의 경우에는 각각 다른 frame에 올려서 사용하면 되겠다.
'컴퓨터(Computer Science) > 운영체제(Operation System)' 카테고리의 다른 글
| 운영체제에서 스와핑(Swapping) (0) | 2020.06.10 |
|---|---|
| Virtual Memory, 가상메모리 [운영체제] (0) | 2020.06.08 |
| Memory Management, 메모리 할당 방식 [운영체제] (0) | 2020.06.06 |
| 동기화를 위한 하드웨어 지원, Hardware Support for Synchronization (0) | 2020.06.04 |
| Segmentation, 세그먼트, 불연속 메모리 할당 [운영체제] (0) | 2020.06.03 |