Memory Management
...이어서 진행됨
- Page Table을 2단계만 사용할 수 있는 건 아니다. 다단계로 사용할 수 있다. 프로세스의 주소 공간은 매우 클 수 있기 때문에 Address Space가 더 커지면 다단계 페이지 테이블이 필요. 이를 Multilevel Paging이라고 한다. 한 번 주소변환을 하려면 여러 개의 페이지 테이블을 거쳐야 하며, 4단계 페이지 테이블의 경우 5번의 메모리 접근이 필요하다(4번은 주소 변환, 1번은 실제 데이터 접근). 예를 들어 메모리 접근 시간이 100ns라면 500ns가 소요될 것이다. 하지만 전 시간에 배운 TLB(Translation Look-aside Buffer)를 이용하면, 대부분의 주소 변환 시간 동안 TLB에서 이루어지기 때문에 그 소요가 적다.
Valid (v) / Invalid (i) Bit in a Page Table
- Page Table의 Entry는 프로세스 주소 공간이 가질 수 있는 최대 페이지 수만큼 생겨야 한다. Table에서는 인덱스를 통해 접근해야 하기 때문. Valid bit가 세팅되어 있다면 정상적으로 사용이 되고 있는 페이지이고(접근 허용), Invalid bit가 세팅되어 있다면 해당 페이지가 이 프로세스에서는 사용되지 않고 있거나, 메모리에 올라가 있지 않고 Backing store(Swap area)에 저장되어 있는 페이지라는 것이다(접근 불가).
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에 들어가 있다.
-
문제점과 효용성 : 페이지 테이블의 공간을 줄이고자 사용한다. 문제는 시간적인 Overhead가 있다. 전부 다 Search를 해야만이 물리적 주소에서 해당 프로세스의 Page p가 어디있는지 알 수 있기 때문이다. 따라서 Inverted Page Table에는 process id(pid)와 Page 번호 p를 함께 저장되어야 한다. 어찌 되었든 Inverted Page Table을 활용하면 공간적인 문제는 해결할 수 있지만 시간적인 문제가 발생하기 때문에 이것을 또 해결하기 위해서는 associative register를 사용하여 이 Entry들을 병렬적으로 동시에 검색할 수 있는 기능이 필요하다.
Shared Page
-
프로세스를 구성하는 페이지들 중에는 다른 프로세스들과 공유할 수 있는 페이지가 존재한다. Word 프로그램 3개를 실행한다고 한다면, 프로그램 Code부분은 서로 같은 것을 사용할 수 있다. 이런 식으로 Share 할 수 있는 코드들을, 별개로 물리적인 메모리에 올리는 것이 아니라, Shared Code에 대해서는 한 Copy만 물리적인 메모리에 올리는 것이 바로 Shared Page이다.
-
Shared Code, 혹은 Re-entrant Code(=재진입 가능 코드, Pure Code)라고 하며 Shared Code의 성립 조건은 두가지가 있다.
- read-only로 하여 프로세스 간에 하나의 code만 메모리에 올린다.
- Shared Code는 모든 프로세스의 logical address space에서 동일한 위치에 있어야 한다(순서 동일).
-
이와 반대는 Private code and data라고 하며 각 프로세스들은 독자적으로 메모리에 로드하게 된다. Private data는 logical address space 어느 곳에 올라와도 무방하다.
Segmentation
- 세그먼테이션 기법은 프로세스가 구성하는 주소 공간을 의미 단위로 (Code, Data, Stack,...)으로 쪼갠 것. 작게는 프로그램을 구성하는 함수 하나하나를 세그먼트로 정의할 수 있고 크게는 프로그램 전체를 하나의 세그먼트로 정의 가능하다. 일반적으로는 당연히 Code, Data, Stack 부분이 하나씩의 세그먼트로 정의된다. (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으로 구성된다. 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 : 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가 걸리게 된다.
- egment의 길이가 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에서 상당히 효과적.
