[운영체제 #13] Segmentation and Paging

Segmentation

segmentation concept

 

segmentation은 프로그램을 segment로 나누어 관리하는 방식이다. 여기서 segment table을 사용하는데, 이 테이블로 각 segment의 시작 주소와 크기를 관리한다. 그래서 segment 번호를 이용해 segment의 메모리 주소를 찾는데 사용된다.

segmentation architecture

 

• s : segment 번호, 이걸로 segment의 base값을 찾는다.
• d : offset, segment의 최대 크기, d값이 limit보다 작아야만 유효하므로 검사한다.
• 이 둘을 더해서 최종 메모리 주소를 찾는다.

segment table은 프로세스마다 다르게 가지므로, context switch 발생 시 테이블도 변경돤다. 따라서 다음 레지스터들로 테이블 정보를 기억한다.

• STBR(Segment-table base register) : segment table의 시작 주소를 저장하는 레지스터
• STLR(Segment-table length register) : segment table의 길이를 저장하는 레지스터
• 이는 s가 STRL보다 무조건 작아야 합법적이라고 해석이 가능하다.

또한 segmentation은 segment table에는 다음과 같은 요소가 포함되어 protection에 유리하다.

• 유효성 비트 : 0이면 불법 segement로 간주
• 읽기/쓰기/실행 권한 : 각 segment에 대해 개별적인 권한 설정 가능.
• 보호 비트 : segment 접근 권한을 정의

이 밖에도 segment는 논리적인 단위로 분리되어 있기 때문에 segment 수준에서 다른 프로세스와 코드 공유가 더 쉽고, segment의 길이가 가변적이라 메모리 공간을 보다 유연하고 효율적으로 사용 가능하다는 장점이 있다.

 

하지만 단점도 존재하는데, 서로 다른 크기의 모든 segment들을 메모리에 넣기 위해 segment 사이즈에 맞는 공간을 찾아야 한다. 이렇게 배치하는데 오랜 시간이 소요되고, segment table이 필요하다.

 

또한 contiguous allocation은 logical address를 physical address로 바꾸는데 계산을 2번만(비교 후 덧셈) 거치면 되지만, segmentation에서는 s로 segment table에서 base를 찾는 과정이 있어서 처리속도가 반으로 감소한다.

---

Paging

 

segmentation과 동일하게 외부 단편화를 해결하기 위해 제시된 방법이지만, segmentation과 다르게 고정된 길이의 블럭으로 나누어 메모리를 관리하고, 이 나눈 블럭을 page라고 한다.

Paging Concept

 

프로세스 A를 실행하기 위해 페이지 4개가 필요한 상황인데, 실제 physical 메모리에서 segmentation과 다르게 사이즈는 고려하지 않고 페이지 자리가 남아있는지만 확인하여 할당한다.

 

여기서도 프로세스마다 서로 다른 page table을 가지고 있는데, physical 메모리는 고정된 길이의 frame으로 나누어 지고 해당 프로세스의 page table에 할당된 페이지 별로 frame 번호를 부여한다.

Paging Architecture

 

• p : page 번호, 이 번호로 page table에서 frame 번호인 f를 찾는다.
• d : offset인데, physical address로 바뀌더라도 값은 그대로다. 이는 page frame의 사이즈가 2의 제곱꼴이기 때문에 가능한 것이다.
• 아까와 다르게, 비교와 덧셈하는 연산이 불필요해졌다. 이로 인해 처리 속도가 증가한다.

또한 Paging 기법에서 페이지의 크기는 하드웨어인 physical memory에 의해 정의되고, address에서 p와 d로 나뉘는 기준은 다음과 같다.

logical memory의 사이즈가 2^m 바이트이고, page 사이즈가 2^n바이트라 할 때,

• 페이지 번호(p) :  상위 m-n비트
• 페이지 오프셋(d) : 하위 n비트

Paging Example

logical memory는 16byte이므로 m은 4이고, page의 사이즈는 4byte이므로 n은 2이다.
또한 physical memory는 32byte이므로 4byte의 8개의 페이지가 존재한다.
위 그림에서 논리적 주소 11은 이진수로 1011이므로, page 번호는 10 = 2, 주소 d는 11 = 3이다.
page table에 따르면 2번 page는 1번 frame과 대응하므로, 실제 메모리 주소는 1 * 4 + 3 = 7이다.

Free-frame List

 

Paging 기법에서는 free-frame list로 비어있는 frame 번호를 관리하는데, 위 그림처럼 새로운 프로세스가 4개의 페이지를 요구하면 free-frame list에 남아 있는 frame 번호를 할당해준다.

 

그러나 Paging도 Segmentation에서 연산이 없어졌을 뿐이지, page 번호로 frame 번호를 찾는 과정에서 메모리 접근을 한번 더 요구하기 때문에 시간이 오래 소요되는건 마찬가지다. page table도 segment table과 마찬가지로 메인 메모리에 존재하기 때문이다. 따라서 associative memory 혹은 TLBs(translation look-aside buffers)를 사용한다.

TLBs Concept

 

기존 방식은 p를 넣으면 일반메모리 속에서 page table에 들어가 f를 찾는다. 그러나 TLB를 이용하면 메모리에 접근할 필요 없이 더 빠르게 frame 번호를 찾을 수 있다. TLB는 캐시와 비슷한 개념이라 할 수 있는데, 최근 읽었던 page table을 매핑하여 저장한다.

 

실제로는 TLB와 page table은 동시에 작업을 진행한다. 만약 TLB에 번호가 존재한다면 TLB hit이 되어 TLB로 바로 frame 번호를 찾고, TLB에 존재하지 않으면 TLB miss가 되어 이번만 page table을 사용한 다음 다음번엔 TLB hit이 나오도록 대응하는 frame 번호를 같이 TLB에 저장한다.

 

그러나 Paging도 고정된 길이로 메모리는 나누다 보니 메모리 낭비가 발생하는 내부 단편화를 완전히 해결하지 못한다는 단점이 존재한다.