contents
Multilevel Paging and Performance
프로그램의 주소 공간이 굉장히 넓기 때문에 3, 4단계 이런 식으로 점점 더 여러 단계의 페이지 테이블을 사용하는 게 가능해졌다.
N단계 페이지 테이블은 테이블을 위한 공간을 줄일 수 있다.
하지만, 주소 변환을 위해서 여러 단계를 거쳐야 하는 문제 발생•
페이지 테이블이 물리적인 메모리 상에 있기 때문에 메모리를 한 번 접근하기 위해서 주소 변환을 위해서 메모리에 4번 접근해야한다. → 페이지 테이블이 메모리 상에 있기 때문에
•
주소 변환 후 실제 원하는 데이터 접근을 위해서 메모리 접근
4단계 테이블 ▶️ 4 주소 변환 + 1 데이터 접근 = 5번 접근
if, 메모리 접근 시간이 100ns라고 한다면, 500ns가 걸린다
⚠️ 굉장히 시간 오버 헤드가 크다.
Plain Text
복사
TLB : 주소 변환을 전담해주는 일종의 캐시 메모리
•
4단계 페이지 테이블을 사용하면 시간은 오래 걸릴 수 있지만 대부분의 주소변환은 TLB를 통해서 직접 이루어지지 때문에 다단계 페이지 테이블을 사용해도 시간이 지나치게 오래 걸리지 않음
example)
TLB를 사용하는 경우에 TLB를 통해서 주소 변환이 되는 경우(바로 메모리 접근 가능)가 98%라고 하면 메모리 접근하는 시간이 얼마 정도 걸리겠는가?
메모리 접근 시간 : 100ns
TLB 접근 시간 : 20ns
4단계 페이지 테이블이기 때문에 페이지 테이블을 4번 거쳐야 한다.0.98 * 120(메모리 : 100ns + TLB : 20ns) + 0.02(TLB에서 주소 변환 실패한 경우) * 520(메모리 : 500ns + TLB: 20ns[없는걸 확인]) = 128ns
평균적으로 128ns메모리 접근하는 시간이 100ns이기 때문에 주소 변환을 위해서 28ns만 추가적으로 든다.
대부분 TLB를 통해서 주소 변환을 한다고 치면 크게 오버헤드가 드는 일은 아니다.
Valid(v) / Invalid(i) Bit in a Page Table
논리적 메모리, 페이지 테이블, 물리적 메모리
사실 페이지 테이블에 주소 변환 정보만 들어있는 것이 아니고 부가적인 비트가 entry마다 저장되어 있다.
valid-invalid bit
6, 7번 페이지 | 지금은 사용하지 않는 페이지, 하지만 엔트리가 존재한다. |
why? | 프로그램의 주소 공간이 가질 수 있는 maximum 사이즈만큼 페이지 테이블 엔트리가 생겨야 하기 때문에 프로그램 페이지의 개수만큼 엔트리가 존재하게 된다. |
valid-invalid bit | 테이블(Array)은 엔트리만큼의 index가 생겨야 하기 때문에 6, 7페이지를 포함한 모든 엔트리가 만들어진다. 없는 페이지의 경우에는 valid-invalid bit를 invalid로 표시하게 된다. |
why? | 값에 0이 들어가 있으면 그게 진짜 0번째 프레임을 말하는 것인지 아니면 이 페이지에 대한 값이 없다는 의미인지 알 수가 없다. 따라서 valid-invalid bit로 표시를 해주는 것 |
valid
•
이 페이지 entry에 가면 0번째 페이지가 2번째 프레임에 실제로 올라와 있다는 의미이다.
invalid
1.
해당 페이지가 이 프로그램에 의해서 사용이 되지 않는다는 의미
2.
해당 페이지가 물리적인 메모리에 있지 않고 swap area(하드 디스크 packing store)에 있다는 의미
주소 변환을 시도했을 때 물리적인 메모리 아무곳에도 없다. 그러면 invalid로 표시.Memory Protection
Protection의 의미
[애초에 없는 일] 프로세스마다 페이지 테이블을 각각 가지고 있기 때문에 다른 프로세스가 페이지 테이블을 건들이는 문제는 애초에 일어나지 않는다.
어떤 연산에 대한 접근 권한이 있는지를 나타내는 것코드, 데이터, 스택 중에서 코드 같은 경우는 애초에 내용이 바뀌면 안된다.
코드 : 원래 있는 내용을 읽어서 instruction를 실행하는 용도
[ read-only ]
데이터, 스택 : 쓰고 업데이트하는 용도
[ read, write ]
Protection bit
이 페이지에 대해서 읽기 권한이 있는지, 쓰기 권한이 있는지, 연산에 대한 권한을 나타내는 비트
Inverted Page Table
지금까지 페이지 테이블에서 문제가 되는 점
굉장히 많은 용량을 차지 하고 있다•
엔트리가 100만개 이상
•
주소 변환을 위한건데 페이지 테이블 자체가 메모리 용량을 많이 차지하게 된다.
•
address space가 허용하는 한도만큼 페이지 테이블 엔트리가 만들어져야 하고 각 프로세스별로 주소 변환을 해야하기 때문에 각 프로세스별로 페이지 테이블 생성
공간 오버헤드가 큼이걸 막아보자는 마음으로 나온것 : Inverted page table
원래의 페이지 테이블을 통한 주소 변환을 역발상으로 뒤집은 것
•
시스템 안에 페이지 테이블이 딱 하나 존재
•
페이지 테이블의 엔트리가 물리적인 메모리의 페이지 프레임 갯수만큼 존재
원래 논리적인 페이지 번호가 있으면 해당하는 엔트리에 가서 프레임 번호가 있어서 주소 변환하는 방식이 불가능
why?
역방향 페이지 테이블은 들어가는 내용이 반대로 되어 있다.
•
첫번째 엔트리에는 첫번째 페이지 프레임에 들어가는 논리적인 페이지 번호가 들어가 있음
•
두번째 엔트리에는 두번째 페이지 프레임에 들어가는 논리적인 페이지 번호가 들어가 있음
•
페이지 프레임의 f번째 엔트리에 가면 논리적인 페이지 번호가 나오도록 한 것
주소 변환이라는 것 논리적 메모리를 물리적 메모리로 바꾸는 것
하지만 Inverted Page Table은 물리적 메모리를 논리적 메모리로 바꾼다. 주소 변환 방법
•
논리 주소를 가지고 물리 주소를 알아내야 하기 때문에 논리적 메모리의 p가 물리적 메모리의 어디에 올라가야 하는지 찾으려면 엔트리를 다 찾아봐야 함.
•
테이블은 index를 통해서 위에서 p번째 떨어지는 곳으로 바로 찾는게 장점인데 Inverted Page Table에서는 그런 장점이 없음.
→ 전부 검색해야지만 주소 변환이 가능
왜 쓰냐?
페이지 테이블을 위한 공간을 줄이고자 하는 것 → Inverted Page Table에서는 시스템에 하나 밖에 없기 때문에
시간적인 오버헤드가 존재 → 전부 서치하기 때문에
논리적인 페이지 번호만 저장하는 것이 아니고 p가 어떤 프로세스의 p번째 페이지인지, 그 프로세스의 아이디(pid)를 같이 저장해야 한다.
1.
CPU가 논리 주소를 주면 이 논리 주소에 있는 페이지 번호 p가 페이지 테이블에 어디에 있는지 검색
2.
p가 여러개 있을 수도 있기 때문에 프로세스의 pid를 같이 줘서 그 프로세스의 p번째 페이지가 어디있는지 찾음
3.
주소 변환은 찾아진 위치가 위에서 몇 번째 entry인지 봐서 위치에 해당하는 번호를 페이지 프레임 번호로 넣으면 주소 변환이 끝나게 된다.
공간 줄이겠다고 일일이 검색하는건 오버헤드가 크다
보통은 inverted page table를 순차적으로 찾도록 만드는 것은 적절하지 않고 TLB에서 설명한 것처럼 associative register를 사용해서 엔트리들을 병렬적으로 동시에 검색할 수 있게, 그냥 메모리에 넣는 것이 아니라 associative register라는 별도의 하드웨어에 집어넣어서 동작을 하게 하면 순차적인 탐색에 시간 오버헤드를 줄일 수가 있게 된다.
Shared Page
프로그램을 구성하는 페이지들 중에는 다른 프로세스들하고 공유할 수 있는 페이지
share 할 수 있는 코드 = shared code = re-entrant code = pure code
•
이 프로그램들이 “같은 코드를 가지고 프로그램을 돌린다” 라고 한다면 동일한 코드 부분을 가지고 실행 가능
◦
각각 물리적인 메모리에 별도로 올리는 것이 아니고 shared 가능한 코드에 대해서는 한 카피만 물리적인 메모리에 올리는 것
다른 프로그램에서도 같은 코드를 쓴다.•
공유할 수 있는 코드는 같은 프레임으로 매핑 시켜서 메모리에 한 카피만 올릴 수 있다.
•
여러 프로세스가 공유할 수 있는 코드 부분을 같은 물리적인 메모리 프레임으로 매핑해주는 기법
•
페이지들을 read-only로 세팅 → 문제가 생길 수 있어서
◦
대신에 물리적인 메모리 한 카피만 올려둠
Private code and data: 프로세스마다 별도로 가져야 하는 데이터는 각각이 다른 프레임으로 매핑되도록 함
shared code의 두 가지 조건
•
read-only 페이지여야 한다.
•
shared code는 동일한 논리 주소에 위치해야 한다.(동일한 물리 주소는 당연한 말)
◦
각 프로세스에서 shared code에 해당하는 페이지 논리 주소가 동일해야 함
◦
why?
일종의 컴파일된 코드에는 주소가 적혀져 있다. 코드 안에는 논리 주소가 적혀있음.
Shared memory를 이용해서 프로세스 간의 interprocess communication(IPC)하는 방법과는 다르다.
•
IPC는 프로세스간의 통신을 목적으로 어떤 페이지를 여러 프로세스에 주소 공간에 같이 맵핑하는 거까지는 Shared memory와 동일하다.
•
read, write를 가능하게 하고 한 친구가 write를 하면 다른 친구가 그걸 읽고(일종의 커뮤니케이션이 목적)
•
여기 있는 shared code는 read-only로 해서 그런 프로세스가 내용을 접근하다가 다른 프로세스에게 영향을 끼치는 문제를 배제한 그런 코드기 때문에 기존의 shared memory에서 얘기한 기법하고는 조금 다르다.
•
shared memory에서는 read, write가 가능한 걸 말했지만 여기서의 shared page는 read-only로 share하는 코드를 공유하는 것
Segmentation
프로그램이 구성하는 주소 공간을 의미 단위(코드, 데이터, 스택)로 쪼갬
→ 더 잘게 쪼개고 싶으면 코드 중에서 함수 별로, 별도의 세그먼트로 구성 가능
Logical address = segment-number + offset
•
각 세그먼트 별로 서로 다른 물리적인 메모리 위치에 올라갈 수 있기 때문에 세그먼트 별로 주소 변환을 해야해서 세그먼트 테이블을 두고 있다.
•
주소 변환을 위해서 base, limit register 두 개를 사용
◦
Segment-Table Base Register(STBR) : segment table의 위치
◦
Segment-Table Length Register(STLR) : 프로그램이 사용하는 segment의 수
1.
CPU가 논리 주소를 주면 두 부분으로 나뉜다.(segment 번호와 offset)
2.
segment table의 시작 위치는 register가 가지고 있다.
3.
거기서부터 segment 번호만큼 떨어진 entry에 들어가면 이 세그먼트가 물리적인 메모리에 어떤 번지에 위치하는지 가지고 있음
페이징하고 다르게 entry에 2가지 정보를 가지고 있다.
1.
물리적인 메모리 상의 시작 위치
2.
limit(세그먼트의 길이) : 세그멘테이션에서는 의미 단위로 자르기 때문에 세그먼트의 길이가 균일하지 않을 수 있기 때문에 세그먼트의 길이가 얼만지 테이블 entry에 같이 가지고 있게 된다.
주소 변환을 할 때 크게 두 가지를 체크해보아야 한다.
1.
CPU에 주어진 주소에서 논리주소의 세그먼트 번호가 세그먼트 테이블 length register의 갯수보다 작은 값인지 확인해서 그 값보다 큰 세그먼트를 요청하면 이거는 잘못된 시도이기 때문에 trap이 걸림
2.
세그먼트를 통해서 주소 변환을 하는데 세그먼트의 길이가 세그먼트 안에서 떨어진 offset보다 작을 경우, trap 발생
정상적인 요구일 경우, 주소 변환을 하는데
•
주소 변환은 segment 시작 위치에다가 offset를 더해서 주소 변환을 함
•
거기서부터 d만큼 떨어진 위치에 가면 원하는 데이터 존재
•
세그먼트의 길이는 이 offset으로 표현할 수 있는 비트수 이상은 안된다.
세그먼트 크기가 다 다르기 때문에 이 세그먼트가 어디서 시작하는지 정확한 바이트 단위 주소로 매겨줘야 한다.
•
세그먼트의 크기가 균일하지 않기 때문에 사용하지 않는 메모리 공간이 군데 군데 생겨난다.
세그멘테이션 기법의 단점•
크기가 균일하지 않기 때문에 first fit, best fit를 써야 한다.
•
외부 조각이 발생하는 문제가 있음
세그멘테이션 기법의 장점•
의미 단위로 쪼개기 때문에 의미 단위로 일을 할 때는 Segmentation 방식이 효과적이다.
example )
예를 들면 Protection를 하는 경우에 우리가 어떤 부분은 read only로 되어 있고 write인지 의미 단위로 권한 부여를 하게 된다.
페이지에서는 페이지 크기 단위로 자르기 때문에 코드와 다른 것이 섞여 들어갈 수도 있는건데, 의미 단위로 자를시에는 그런 일이 없다.
Sharing, Protection 모두 의미 단위로 하는 것이 Paging보다 유리하다.•
의미 단위로 하는 공유, 보안에 있어서 세그먼트가 유리하지만 세그먼트는 크기가 균일하지 않아서 이런 allocation 상에 문제가 발생한다.