- 본 글은 이전에 사용하던 영상 강의 필기 앱인 'Slid'에서 필기 했던 내용을 Velog로 옮긴 내용입니다.
- 본 글은 이화여대 반효경 교수님 2017학년도 1학기 운영체제 강의를 기반으로 작성되었습니다.
- 강의 링크 : http://www.kocw.net/home/search/kemView.do?kemId=1226304
물론 Page Table을 2단계만 사용할 수 있는 건 아니다. 다단계로 사용할 수 있다. 프로세스의 주소 공간은 매우 클 수 있기 때문에 Address Space가 더 커지면 다단계 페이지 테이블이 필요하다. 그것을 Multilevel Paging이라고 한다. 그렇지만 한 번 주소변환을 하려면 여러 개의 페이지 테이블을 거쳐야 하며, 4단계 페이지 테이블의 경우 5번의 메모리 접근이 필요하다(4번은 주소 변환, 1번은 실제 데이터 접근). 예를 들어 메모리 접근 시간이 100ns라면 500ns가 소요될 것이다. 하지만 전 시간에 배운 TLB(Translation Look-aside Buffer)를 이용하면, 대부분의 주소 변환 시간 동안 TLB에서 이루어지기 때문에 그 소요가 적다. TLB hit ratio가 98%이고 TLB 접근 시간이 20ns, 메모리 접근 시간이 100ns라면,
EAT(Effective memory Access Time) =
0.98 * 120(20ns 만에 주소변환, 100ns 메모리 접근 = 20ns + 100ns)
+
0.02 * 520(100ns * 4단계(-> 왜? 4단계 페이지 테이블이라서?), TLB에 있는지 체크 20ns, 메모리 접근 100ns) --> 여기 부분 이해 안됨. 강의에서 이해하기
=
128 nanoseconds(ns).
결과적으로 주소 변환을 위해서는 28ns가 소요된다고 할 수 있다.
* Valid (v) / Invalid (i) Bit in a Page Table *
앞서 Page Table의 Entry는 프로세스 주소 공간이 가질 수 있는 최대 페이지 수만큼 생겨야 한다고 했다. 그 이유는 Table에서는 인덱스를 통해 접근해야 하기 때문이었다. <그림 1>을 살펴보자. 6, 7번 Page는 없지만 Table의 Entry로는 6과 7이 만들어져야 한다. 이때 6번과 7번 페이지에 해당하는 값은 없기 때문에 Invalid bit로 세팅해 놓는다는 것이다. 그래서 Valid bit가 세팅되어 있다면 정상적으로 사용이 되고 있는 페이지이고(접근 허용), Invalid bit가 세팅되어 있다면 해당 페이지가 이 프로세스에서는 사용되지 않고 있거나, 메모리에 올라가 있지 않고 Backing store(Swap area)에 저장되어 있는 페이지라는 것이다(접근 불허).
* Protection bit *
이 Protection bit는 다른 프로세스가 해당 페이지를 보지 못하게 하는 용도가 아니다. 그 이유는 당연히 알 것이라 생각한다. 애초에 어떤 프로세스는 자신의 영역밖에 보지 못하기 때문이다. Protection bit는 page에 대한 접근 권한 (read/write/read-only)을 나타내는 것이다. 이 페이지 중에는 해당 프로그램의 code 부분을 담고 있는 페이지도 있고, data나 stack을 담고 있는 페이지도 있을 것이다. 그중 Code 부분을 담고 있는 페이지는 수정되어선 안되기 때문에 Code 부분의 경우 read-only의 권한만 부여될 것이고, Data나 Stack을 담고 있는 페이지는 Read와 Write 권한이 부여될 것이다.
* Inverted Page Table *
등장 배경 :
Page Table의 문제는 굉장히 많은 용량을 차지하고 있다는 것이다. Address Space가 허용하는 한도 만큼의 Page Table Entry가 만들어져야 하고, 프로세스마다 Page Table들이 만들어져야 한다는 문제가 있다. 이러한 문제를 해결하고자 Inverted Page Table이 등장하였다.
아키텍처 :
원래는 Page Table이라는 것은 프로세스마다 존재했다. 그러나 이 Inverted Page Table은 System안에 Page Table이 딱 하나 존재한다. 그리고 이 Page Table의 Entry가 프로세스의 페이지 개수만큼이 아니라 물리적인 메모리의 Page Frame 개수만큼 존재(??)한다. 그리고 첫 번째 Entry는 물리적인 메모리의 첫 번째 Frame을 나타내고, 두 번째 Entry는 두 번째 Frame을 나타내는 방식이다. 그런데 주소 변환을 하려면, 페이지 번호를 보고, 페이비 번호 인덱스에 바로 접근하는 방식인데 이 방법으로는 그것이 불가능하다. 이 역방향 페이지 테이블에서는 첫 번째 Entry에는 첫 번째 Frame에 들어가는 논리적인 Page 번호가 들어가 있고, 두 번째 Entry에는 두 번째 Frame에 들어가는 논리적 Page 번호가 들어가 있는 식이다. 그러나 주소 변환이라는 것은 Logical Address를 Physical Address로 바꾸는 것이다. 따라서 이 방법을 이용하면, 프로세스 번호 pid인 프로세스의 Page p가 어디에 들어가 있는지 찾기 위해서는 Page Table의 모든 Entry를 전부 뒤져야 한다. 그래서 만약 f번째 인덱스 Entry에서 찾았다면 이 프로세스의 Page p는 f번째 Frame에 들어가 있다는 것을 알 수 있다. <그림 2를 참조하자>
문제점과 효용성 :
그럼 도대체 이걸 왜 쓰는가? 페이지 테이블의 공간을 줄이고자 하는 것이다. 문제는 시간적인 Overhead가 있다. 전부 다 Search를 해야만이 물리적 주소에서 해당 프로세스의 Page p가 어디있는지 알 수 있기 때문이다. 따라서 Inverted Page Table에는 process id(pid)와 Page 번호 p를 함께 저장되어야 한다. 어찌 되었든 Inverted Page Table을 활용하면 공간적인 문제는 해결할 수 있지만 시간적인 문제가 발생하기 때문에 이것을 또 해결하기 위해서는 associative register를 사용하여 이 Entry들을 병렬적으로 동시에 검색할 수 있는 기능이 필요할 것이다.
* Shared Page *
프로세스를 구성하는 페이지들 중에는 다른 프로세스들과 공유할 수 있는 페이지가 존재한다. <그림 3>예시를 통해 함께 살펴보자. P1, P2, P3가 있는데 이 프로세스들이 만약 같은 코드를 가지고 실행된다면, 예를 들어 Word 프로그램 3개를 실행한다고 한다면, 프로그램 Code부분은 서로 같은 것을 사용할 수 있다. 이런 식으로 Share 할 수 있는 코드들을, 별개로 물리적인 메모리에 올리는 것이 아니라, Shared Code에 대해서는 한 Copy만 물리적인 메모리에 올리는 것이 바로 Shared Page이다. 그래서 P1, P2, P3의 Page Table Entry 네 개 중에 앞의 세 개는 전부 3, 4, 6으로 대치된다(순서 동일). 이것이 바로 공유가능한 Shared Page인 것이다.
이것을 다른 말로 Shared Code, 혹은 Re-entrant Code(=재진입 가능 코드, Pure Code)라고 하며 Shared Code의 성립 조건 두 가지에 유의하자. 1. read-only로 하여 프로세스 간에 하나의 code만 메모리에 올리게 된다. 그리고 2. Shared Code는 모든 프로세스의 logical address space에서 동일한 위치에 있어야 한다(순서 동일). 2번이 성립해야 하는 이유는 9-1강 처음에서 Address Binding을 할 때, 코드 안에 들어가 있는 논리적 주소가 다르다면 동일한 물리적 메모리에 올라갈 수 없기 때문이다. 이와 반대되는 개념으로 Private code and data라고 하며 각 프로세스들은 독자적으로 메모리에 로드하게 된다. 당연하게도 Private data는 logical address space 어느 곳에 올라와도 무방하다.
- Segmentation
세그먼테이션 기법은 프로세스가 구성하는 주소 공간을 의미 단위로 (Code, Data, Stack,...)으로 쪼갠 것이다. 작게는 프로그램을 구성하는 함수 하나하나를 세그먼트로 정의할 수 있고 크게는 프로그램 전체를 하나의 세그먼트로 정의 가능하다. 일반적으로는 당연히 Code, Data, Stack 부분이 하나씩의 세그먼트로 정의된다.
Segment는 다음과 같은 logical unit들이다. 즉, 다음과 같은 것들이 Segment가 될 수 있다는 것이다.
ex) main(), function, global variables, stack, symbol table, arrays
* Segmentation Architecture (세그먼테이션에서 주소 변환) *
이 기법에서 Logical address는 <segment-number, offset>으로 구성된다.
그리고 Segment별로 주소 변환을 해야 하기 때문에 Segment 마다 Segment Table의 Entry가 존재한다. 즉, Segment Table의 Entry 개수는 Segment의 개수이다. 각 entry는 base와 limit으로 구성되는데, 주소 변환 시에 사용되는 Base register와 Limit register가 기억나는가? Segmentation 기법에서는 Segment-table base register (STBR)과 Segment-table length register(STLR)로 사용되며 STBR은 base, 즉, starting physical address of the segment(Segment table의 시작 위치)를 담고 있고 STLR은 limit, 즉, length of the segment(프로그램이 사용하는 segment의 수)를 담고 있다.
Segmentation Architecture :
<그림 4>를 보자. CPU가 논리적 주소를 주게 되면 (s, d), Segment Table의 시작 위치는 STBR 레지스터가 가지고 있으므로 거기서부터 s에 해당하는 인덱스 entry에 가면 해당 세그먼트가 물리적 메모리 주소에 어디에 매핑되는지 그 정보를 가지고 있다. 그런데 Segmentation 기법은 entry에 두 가지 정보를 갖고 있다(limit과 base). Segmentation 기법에서는 Paging 기법에서와는 다르게 각 Segment의 길이가 모두 다를 수 있기 때문에 해당 Segment의 길이가 얼마인지 저장해야 하기 때문이다.
또한, Segment에서는 Addressing error가 발생할 두 가지 상황이 존재한다.
첫 번째로는 STLR은 Segment의 수를 담고 있기 때문에 만약 (s, d)에서 s가 Segment의 개수보다 크다면 잘못된 정보가 넘어온 것이므로 trap : addressing error가 걸리게 된다.
두 번째로는 Segment의 길이가 Segment Table의 Entry 중 limit에 담겨있는데 이 값보다 (s, d)의 d가 더 크다면 마찬가지로 trap : addressing error가 걸리게 될 것이다.
이를 통과한다면 Segment의 시작 주소 Entry인 Base에다가 d값을 더해서 주소 변환을 하게 되는 것이다.
* Pros/Cons *
Allocation(Cons) : Paging에서는 Logical address에서 이미 Page의 개수가 정해져 있기 때문에 offset의 최대 길이 또한 정해져 있다. 그러나 Segmentation에서 Segment길이는 d인 offset으로 표현할 수 있는 비트 수 이상은 표현이 불가능하다. 즉, d값이 Segment길이를 제한하는 역할을 한다. 또한 Paging에서는 어차피 물리적 주소도 Page와 같은 크기인 Page Frame으로 잘려 있기 때문에 인덱스만 저장하면 되지만, Segmentation에서는 Segment마다 길이가 다르기 때문에 정확한 시작 주소를 Segment Table의 Entry인 base에 담고 있어야 한다. 즉, 크기가 일정치 않을 때 가변 분할 방식(연속 할당 기법)에서 hole의 발생으로 생기는 문제인 external fragmentation(외부조각 - 프로그램의 크기가 분할의 크기보다 커서 다른 분할로 프로그램이 들어가야 할 때)이 발생한다. 따라서 First fit / Best fit 기법을 사용해야 한다.
Protection(Pros) : 대신 장점은 분명히 있다. Segmentation은 의미 단위로 쪼개는 것이기 때문에 Protection을 할 때, 일반적으로 의미 단위로 권한을 부여한다. 특히 Read/Write/Execution 권한을 설정하는 데는 의미적인 단위로 그것을 부여해야 할 것이다. 이런 상황에서 Segmentation은 상당히 유리할 것이다. Paging에서는 Code와 Data가 같이 들어갈 수 있어서 Protection 권한 부여에 관한 복잡한 문제들이 발생할 수 있지만 Segmentation에서는 그것을 쉽게 해결할 수 있다.
Sharing(Pros) : Sharing에서도 Segmentation이 유리하다. 보통 Sharing도 의미단위로 하게 된다. 그러나 Paging에서는 의미 단위의 구분이 전혀 되지 않기 때문에 Sharing 문제가 상당히 복잡하게 된다. 반면 Segmentation에서는 이미 의미 단위로 구분되어 있기 때문에 Sharing에서 상당히 효과적이다.
