3) 페이징과 세그먼트(Paging and Segment)
3-1) 페이징 (Paging)
프로세스가 사용하는 주소 공간을 여러 개로 분할하여 비연속적인 물리 메모리 공간에 할당, 가상 메모리를 모두 같은 크기의 블록으로 나누어 메모리를 관리하는 방식.
단위
프레임 : 실제 메모리 공간 (4KB)
페이지 : 프로세스의 메모리 공간 (4KB)
프레임 사이즈 = 페이지 사이즈
★ 페이지 테이블 내에 프레임과 페이지가 서로 매핑이 되어 있어서 페이지 테이블을 참조하여 실제 메모리에 접근하게 된다.
★ 문제 : 매번 메모리의 페이지 테이블을 먼저 읽어야 하므로 메모리 접근 시간이 두 배가 된다. => 페이지 테이블의 캐시 사용
3-2) 세그먼테이션 (Segmentation)
프로세스가 필요로 하는 메모리 공간을 분할하여 비연속적인 물리 메모리 공간에 할당하는 방식. 즉, 각 영역들의 기능, 권한, 필요한 공간의 크기가 모두 다르기에 세그먼테이션 기술로 각각 다른 크기로 분할하여 효율적인 메모리 관리가 가능하도록 한 것이다.
단위 : 세그먼트(서로 다른 크기)
페이징과의 차이
논리적 의미에 부합하도록 세그먼트들의 크기가 서로 다름.
크기가 다 다르기 때문에 메모리를 페이징 기법에서처럼 미리 분할해 둘 수 없고, 메모리에 적재될 때 빈 공간을 찾아 할당.
논리 주소 공간을 세그먼트 집합으로 정의.
세그먼트 테이블
사용자가 정의한 주소를 실제 주소로 맵핑하는 정보를 저장.
개별 세그먼트는 항목별로 Base(세그먼트 시작 주소) + Limit(세그먼트 길이)의 정보를 갖는다.
3-3) 요구 페이징 (Demand Paging)
-> Demanding-page는 실제로 필요한 page만 물리 메모리로 가져오는 방식을 말한다. 필요 page에 접근하기 위해선 가상 메모리 주소에 대응하는 물리 메모리 주소를 찾아내야 한다. 이 때 필요한 것이 페이지 테이블(page table)이다.
페이지 테이블에 valid bit를 두고, 해당 page가 물리 메모리에 있으면 1, 그렇지 않으면 0로 설정한다.
ex) Page fault의 경우
1) 페이징 하드웨어는 page table entry의 valid bit를 보고 invalid인 것을 확인한 후 OS에게 trap으로 알린다.
2) OS는 정말로 메모리에 없는 것인지 아니면 잘못된 접근인지 확인한 후 잘못된 접근이었으면 종료시킨다.
3) Empty frame (free page)을 얻는다.
4) Page를 frame으로 swap한다.
5) 프로세스의 page table과 TLB를 page-in/page-out 된 것을 토대로 재설정한다.
6) Page fault를 야기했던 인스트럭션부터 다시 수행한다.
=> 3) 과정에서 empty frame(free page)을 얻어 와야 하는 상황에서 물리 메모리가 모두 사용 중이라면, 사용 중인 frame 중 하나를 선택해서 page-out (disk로 이동) 시키고, 그 frame을 사용해야 한다.
이처럼 victim frame을 선택하는 과정에서 Page Replacement Algorithm을 사용한다.
3-4) 페이지 교체 정책 (Page Replacement Algorithm)
메모리 공간이 부족하면 특정 페이지를 스왑 하여 교체한다.
※교체 알고리즘
◎ FIFO (First-In-First-Out)
- 메모리에 적재된 시간이 가장 오래된 페이지를 교체 (프레임 개수가 많아지면 페이지 부재 율이 높아지는 현상, Belady의 모순이 된다.)
◎ Optimal Page Replace
- 앞으로 가장 오래 사용되지 않을 페이지를 교체, 들어온 데이터를 쭉 읽어서 앞으로 사용하지 않을 걸 교체
- 다른 모든 알고리즘보다 페이지 부재 율이 낮으면서 Belady의 모순이 발생하지 않는 페이지 교체 알고리즘
- 실제 구현이 불가능하다 : 미래의 페이지 참조를 미리 알아야 함.
- 제안된 알고리즘의 성능을 비교하기 위한 목적으로 사용
◎ LRU (Least-Recent-Used)
- 가장 오랫동안 사용되지 않은 페이지를 교체.
- 최적 페이지 교체 알고리즘에 근사하는 방법, 과거 참조를 기반으로 미래 참조 형태의 근사치를 결정
- 거의 최적 알고리즘에 가까움
- linked-list로 관리
- 고려사항
- 하드웨어의 지원이 필요 : 모든 메모리 참조에 대해 참조 정보를 갱신
- 페이지들을 최근에 사용한 시간 순서대로 나열할 수 있어야 함
◎ LFU (Least-Frequently-Used)
- 참조 횟수가 가장 적은 페이지를 교체
- 참조 횟수가 적은건 앞으로도 안쓸것이다.
- 참조 빈도와 참조 시간은 정확히 일치하지 않습니다.
◎ MFU (Most-Frequently-Used)
- 참조 횟수가 가장 많은 페이지를 교체
- 최근에 참조가 된 페이지는 앞으로 덜 쓸것이다.
- 참조 횟수가 적은 페이지는 최근에 적재되었고 앞으로 참조될 가능성이 높을 것이라는 직관에 의존
※ 자세히 설명하자면 Demand Paging을 가능하게 하는 것은 Locality의 개념이다.
Temporal Locality는 시간적 지역성이라 하며 최근에 접근된 것이 다시 접근되는 것을 말하며, Spatial Locality는 공간적 지역성이며 최근에 접근된 것에 가까운 것이 접근되는 것을 말한다. 따라서 Locality에 의하면 접근되었던 것은 접근될 가능성이 크므로 메모리에 남아있게 되고 그것이 Demand paging의 근본이 된다.
위의 3-3)에서 Page Fault 처리 과정에서 empty frame(free page)을 얻는다고 되어 있다.
물론 empty frame이 있으면 그냥 얻으면 되겠지만 멀티프로세싱 환경에서 실행하다 보면 메모리가 꽉 차있을 경우가 있을 것이다.
이 경우에 앞서 말했듯 어떠한 기준에 의해 페이지 하나를 swap out하고 그 프레임을 할당할 것인지를 정하는 것이 Paging Replacement Algorithm이다.
첫째로 FIFO(First in First out)알고리즘은 가장 오래된 페이지를 없애는 기법으로 공평하기는 하지만 locality가 적용되지 않은 방법이므로 비효율적이다.
다음으로 Optimal 알고리즘이다. 가장 오랫동안 사용되지 않을 것을 victim으로 선정하는 것이 당연히도 가장 합리적이며 효율적이다. 하지만 가장 오랫동안 사용되지 않을 것을 정하는 것은 불가능하므로 이론적인 알고리즘이라 볼 수 있다.
그래서 Optimal 알고리즘과 원리는 유사하지만 반대로 생각한 것이 LRU 알고리즘이다. 가장 오랫동안 사용되지 않았던 페이지는 앞으로도 사용되지 않을 것이라는 가정 하에 victim으로 선정한다.
LRU 방식에는 첫째로 counter를 두어 구현할 수 있다. 카운터에 접근횟수를 기록하는 것이다.
둘째로 더블 링크드 리스트의 스택으로 구현한 뒤 어떠한 페이지가 접근되면 그 페이지를 top으로 올린다. 그리고 만약 victim을 선정해야 하면 bottom에 있는 페이지를 victim으로 선정하게 된다.
하지만 이러한 방식을 쓰면 많은 페이지 엔트리가 존재하는 페이지 테이블에서는 연산이 많아지고 각 엔트리마다 두개의 링크만큼의 공간을 필요로 하므로 비효율적이다.
따라서 Page Table에서는 LRU-approximation 알고리즘을 사용한다. 이 알고리즘은 하드웨어의 도움을 받아 하나의 bit를 두고 이용한다.
페이지들을 queue형태로 나타내고 만약 reference가 일어나면 이 bit를 set한다. 그리고 victim 페이지를 선정할 때는 하나씩 접근하여 bit를 확인한다. 만약 bit가 clear하면 그 페이지를 victim으로 선정하며, set 되어 있으면 그 bit를 clear시키고 다음 페이지를 확인한다. 해당 페이지에 Second-chance를 주는 것이므로 Second-chance algorithm이라고도 한다.
그리고 카운팅을 기반으로 한 MFU, LFU알고리즘이 있다.(설명은 위 참조)
이렇게 Virtual Memory를 사용하면 실제 존재하는 물리적 메모리 공간보다 논리적 메모리 공간이 큰 것처럼 사용될 수 있기 때문에 효율적이다. 그런데 효율적이라는 이유로 멀티프로세싱의 degree를 계속 늘리다 보면 실제 실행하는 시간보다 page replacement를 하는 시간이 더 많아지는 순간이 오게 된다. 이는 CPU Utilization을 떨어뜨리는 원인이 된다.
만약 CPU는 CPU사용률만 보고 이것을 올리기 위하여 멀티프로세싱의 degree를 더 증가시키고 이에 따라서 효율은 극악으로 나빠지게 되는데 이때, 실행 시간보다 페이지 교체 시간이 많아지는 현상을 Thrashing이라 한다.
Thrashing이 발생하는 이유는 locality크기의 합이 실제 메모리의 크기보다 커졌기 때문이다. 따라서 이 Thrashing을 해결하기 위해 Working set model을 적용한다.
Working set model은 locality를 approximate한 것으로 페이지 넘버로 관리한다.
그러다 working set의 크기가 실제 메모리보다 커지면 하나의 프로세스를 종료하는 방식으로 Thrashing이 생기지 않도록 조절할 수 있다.
따라서 Thrashing이 생겼다는 것은 즉 Page Fault가 많아졌다는 것이기 때문에 그것의 정도를 지정하고 Page Fault의 횟수가 어느 한계점을 넘어가면 프로세스를 종료하는 방식으로 구현한다.
<working set model 특징>
| 구분 | 설명 | 특징 |
|---|---|---|
| 원리 | 지역성 가정을 기반으로 동작 | 지역성 기반 |
| 특징 | 과도기, 안정기가 주기적 반복 | 프로세스 변화 |
| 장점 | 1. Multi-Programming 정도 높임 2. CPU 활용률 최적화 | 1. Page Hit rate증가 2. 임계치 극대화 |
| 단점 | 1. Working Set 추적관리 복잡 2. Window 사이즈 설정이 모호함 3. 참조 페이지 Queue 유지관리 | 1. 크기/구성 변화 2. 최적값 모름 3. 메모리관리 복잡 |
Virtual Memory를 사용하게 되면 생기는 부가적인 장점으로 공유 메모리 사용, Copy on write 메커니즘, Memory mapped file이 있다.
여러 프로세스간의 communication의 한 가지 방법으로 공유 메모리를 사용할 수 있는데 demand paging 기법을 사용할 경우 다른 프로세스의 각각의 페이지가 같은 프레임을 가리키도록 하면 공유 메모리를 사용할 수 있다.
또한 COW(Copy-On-Write) 메커니즘은 부모 프로세스를 clone하여 자식 프로세스를 생성하였을 때 처음에는 같은 메모리를 사용하도록 하다가 그곳에 Write가 발생하였을 때 메모리를 copy하는 것으로 이것 또한 공유 메모리처럼 같은 프레임을 가리키도록 하였다가 복사가 되었을때 새로운 프레임을 할당하면 된다.
그리고 Memory mapped file은 file을 접근하는 것을 메모리 접근하듯이 페이지를 할당하여 할 수 있도록 하는 것이며 메모리 접근 속도가 더 빠르므로 효율적이다.
Paging은 동일한 크기를 가지는 page 단위로 메모리를 나누는 것이라 하였다.
반면에 Segmentation은 가변 크기의 단위인 segment로 메모리 영역을 나눈다. 이것은 사용자가 바라보는 관점에서 메모리를 나눈 것이며 일반적인 사용자는 페이지 단위로 메모리를 바라보지 않고 큰 단위단위로 바라보게 된다.
따라서 최근의 컴퓨터는 세그멘테이션 기법과 페이징 기법을 동시에 적용하여 메모리를 접근하게 된다.
