Operating System 11 - Memory Management 2

 Virtual memory (CA에서 배운 것과 동일)

virtual memory : logical address와 physical memory를 분리함으로써 secondary storage도 main memory처럼 사용할 수 있게 하는 것.
virtual address : virtual memory의 주소로, 마치 main memory처럼 사용할 수 있게 해주는 것.

page & segmentation : logical & physical address와 불연속적으로 메인메모리에 로드 한다는 사실을 통해 우리는 어떤 프로그램을 실행하기 위해 반드시 모든 부분을 메인 메모리에 올리지 않아도 된다는 것을 알 수 있다.
따라서 모든 부분이 아니라 그때그때 필요한 부분만 메인 메모리에 올려 실행하도록 할 수 있다. (by OS)
따라서 사용하지 않는 부분의 로드, 파일 읽기 등의 오버헤드를 줄일 수 있다.

Resident set : 현재 메인 메모리에 올라와 있는 프로그램의 부분.
memory access fault : 메인 메모리에 올라와 있지 않은 부분이 필요한 경우
이 경우 OS가 해당 부분의 파일을 읽어와 메인메모리에 로드해야 하므로 해당 프로세스를 잠깐 블락시키고 I/O interrupt를 발생시킨다.
앞서 배운 것 처럼 이렇게 되면 다른 프로세스가 로드되어 실행되고, 해당 인터럽트가 처리되면 블락이 해제되어 계속 수행되게 된다.

이렇게 현재 실행되는 부분만 올리면 더 많은 프로세스를 동시에 수행할 수 있다. 다만, 너무 많이 올리게 되면 fault나는 부분이 많아 비효율적이게 될 수 있다.
또한 이 방법을 사용하면 현재 메모리의 크기보다 큰 프로그램도 실행할 수 있다. (swap in/out 하며) 또한 프로그래밍을 할 때도 시스템의 메모리 크기를 고려하지 않고 해도 된다.
* 앞서 살펴본 것 처럼 만약 이것이 없다면 프로그래머가 직접 어느 부분을 swap in / out 해줘야 할지 모두 결정해야 한다. 그러나 현대 컴퓨터 환경에서는 거의 불가능하다.

simple paging & segment와 virtual paging & segment는 전체를 올리냐 안올리냐의 차이이다.

Locality(지역성) & virtual memory
어떤 프로그램이 실행될 때는 사용되는 부분과 데이터는 cluster 되어 있다. (가까운 것, 최근에 사용한 것들이 다음에 사용될 확률이 높다)
따라서 모든 부분을 메인 메모리에 로드하지 않고도 프로그램을 실행할 수 있다. -> VM scheme이 탄생하였다.
또한 필요하지 않은 I/O 오버헤드도 사라지며 메모리의 크기를 고려하지 않고도 프로그래밍이 가능하게 된다.



Thrashing
앞서 언급한 것처럼 너무 많은 프로그램을 올리게 되면 오히려 page fault가 너무 많이 나 swap in / out에 소비되는 시간이 더 크게 되는 때가 온다. 따라서 multiprogramming의 정도도 고려를 해야 한다. (resident set의 최대 개수)

Support for Virtual memory
HW support : logical -> physical address
SW support : which page/segment should be swapped in or out??

Paging
* modified bit : 만약 수정된 것이 있다면 secondary storage로 I/O를 해야하지만, 변경된 것이 없다면 그냥 바로 덮어써도 된다. (바로 free frame list로 사용 가능)
따라서 modified가 되었다면 swap out할 때 업데이트를 반드시 해야 한다. 그러나 되지 않았다면 바로 빼도 되므로 I/O를 안해도 됨 (성능 개선)

2-level hierarchical page table
page table 접근을 두 단계로 하는 방법. 만약 하나의 테이블만 두면 4GB짜리 프로세스 하나에 대해 4MB page table이 필요하지만, 해당 페이지 테이블도 한 단계를 더 두면 4KB짜리 page table로 접근이 가능하게 된다.
다만 이렇게 되면 한번의 메모리 접근에 두 단계나 거쳐야 하므로 접근 연산이 낭비된다는 점이 있다. 그래도 메모리 활용도 면에서는 더 효율적이게 된다.

Inverted page table (프레임 수만큼 형성)
page address에 따라 페이지 테이블도 같이 커진다. 64bit address의 경우 4kb page를 위한 12bit를 빼고 52bit가 page number가 된다. (2^50이 peta, 52bit면 2^52개의 페이지, 페이지만 32petabyte가 필요)
이를 해결하기 위해 실제 메인 메모리에 저장된 것들만 확인할 수 있는 하나의 page table을 놓아야 한다. (프로세스마다 page table을 가지지 않고 시스템 전체에 대한 page table 하나만 가진다)
이를 위해서는 page number와 control bit외에도 process identifier (어느 프로세스의 페이지 인지), chain pointer (해당 페이지와 연결된 다음 값)

이는 page number와 해시테이블로 형성하며, 만약 같은 해시 값을 가지는 서로 다른 페이지가 있다면 chain pointer를 타고 자신의 것을 찾아가게 된다. 따라서 해시 값을 타고 pid를 비교해가며 자신의 것인지 확인하고, 가리키는 주소의 원하는 값을 가져오게 된다.
페이지 테이블에서 메인메모리를 찾는 것과 반대로, 해시 값으로 물리적인 프레임 주소에 먼저 접근하고, 이 것이 해당 프로세스 것이 맞는지 확인하는 것이므로 inverted라 한다.

어쨋든 page table 접근, main memory 접근의 두 번의 메모리 액세스가 필요. 이를 개선하기 위해 페이지 테이블에 대한 캐시도 만들어 사용한다.

Translation Lookaside Buffer (TLB) : page table에 대한 캐시. 물리적으로 존재.
CPU가 원하는 주소가 먼저 TLB에 있는지 확인(메모리보다 먼저). 만약 있다면 바로 해당 주소의 메인메모리 접근 가능. 만약 TLB miss라면 page table로 가서 메인 메모리에 접근한다. 만약 page table도 fault가 난다면 secondary memory까지 가서 main memory에 로드해야 한다.

- associative mapping : TLB에서는 offset을 사용하여 찾기 어렵기 때문에 한 번에 접근하여 해당 페이지가 있는지 없는지 확인하게 된다. (하나의 화살표가 아니라 갈라진 화살표로 가리킴)

page size
페이지 크기가 작을 수록 내부 단편화가 작아짐. 그러나 한 프로세스 당 페이지가 많아지고, page table이 커진다. 또한 페이지 크기가 작아지면 page fault가 날 확률도 올라간다. (두번의 fault 가능)
페이지 크기가 커지면 위와 반대가 된다.
실제로 secondary memory 등은 block 단위로 i/o를 하는데, page 크기가 클 수록 좋다. (하드디스크가 작은 부분을 찾으며 조금씩 쓰는 것 보다, 하나의 위치에서 한 번에 죽 쓰는게 더 좋다.)
따라서 적절한 페이지 크기와 프레임 크기를 설정하는 것이 중요.

Segmentation
실제로 가상메모리에서는 페이지를 사용하고 세그멘테이션은 딱히 사용하지 않는다. 다만 각 모듈 끼리의 shared/protected 이런 공간을 할당하는 데는 더 좋을 수 있다. 배치도 쉽게 할 수 있다.
이는 프로그래머가 해당 세그먼트들을 확인할 수 있으므로 data structor 등을 모두 볼 수 있다는 장점이 있다.

Combined paging & segmented
각 segment마다 page table이 존재하고, 메인 메모리에 접근. 이 경우 배치를 쉽게 할 수 있고, 원하는대로 관리가 될 수 있으며 내부, 외부 단편화를 모두 줄일 수 있다는 장점이 있다. 그러나 앞서 여러 번의 페이지 테이블과 동일하게 다수의 접근이 필요하므로 일반적으로 잘 사용하지 않는다.



OS software
page fault를 줄이기 위해 page 교체 정책을 결정. 어느 페이지를 교체하고, 어느 페이지를 남겨 놓을 지 잘 선택해야 disk I/O에 대한 오버헤드를 최소화 할 수 있다.

- fetch policy : 누구를 가져와서
- placement policy : 어디에 놓고
- replacement policy : 누구를 교체하고
- resident set management : resident의 크기와 scope
- cleaning policy : 교체된 것을 업데이트 언제 할 것인가
- load control : multiprogramming의 정도(degree) 결정

Fetch policy
1. demand paging : 요청이 올 때, 요구된 녀석만 불러들임. 단, 처음 프로그램이 시작될 때는 fault가 많이 발생할 수 있다. 그리고 프로그램이 진행되면 locality가 좋아져 fault가 줄어든다.

2. prepaging : 미리 가져옴. 요청한 블록과 가까이 있는 것을 동시에 가져와 locality를 최대화 하고, fault를 줄이려 함. 다만, locality의 정도에 따라 fault가 더 심해질 수 있다.

일반적으로 처음 시작할 때와 불러오는 부분이 바뀔 때(fault가 많이 나는 시점)는 prepaging을 사용하고, 나머지는 demand를 쓰면 좋다. (동시에 여러 정책을 사용할 수 있다)

Placement policy
여러 CPU가 서로 다른 메모리를 가지고 있다면, 어느 메모리에 놓는 가 도 중요하게 고려하게 된다.

Replacement policy ( 면접에 자주 나올 수 있음)
새로운 페이지를 가져올 때 자리가 없을 경우 기존 페이지를 교체하는 방법. (버릴 페이지를 선택) 따라서 최대한 앞으로 사용하지 않을 페이지를 선택해야 한다. 그러나 너무 정교한 알고리즘으로 예측할 경우 이에 대한 계산 오버헤드가 발생할 수도 있다. 또한 커널 등 필수적인 페이지에 대해서는 교체가 되면 안되므로 frame locking을 통해 해당 페이지들은 교체하지 않도록 한다.

교체정책은 상황에 따라 어느 것이 최적인지 달라지므로 시스템마다 서로 다른 정책을 사용한다.

1. optimal : 앞으로 미래에 가장 사용되지 않을 것을 교체. 가장 page fault가 적게 발생하게 된다. 그러나 미래는 완벽하게 예측할 수 없으므로 이는 이상적인 상황이고, 다른 알고리즘을 평가하는 척도로 사용된다. (개념적으로)

2. LRU(least recently used) : locality를 차용하여 오랫동안 참조되지 않았던 것은 앞으로도 사용하지 않을 것이라 예측. 따라서 해당 부분에서 이미 떠났으므로 가장 오랫동안 참조되지 않은 것을 교체.
(과거를 통해 미래를 예측하는 방식) 이를 위해서 언제 가져왔는지 time stamp가 있어야 하며 이에 대한 계산과 저장에 대한 오버헤드가 존재할 수 있다. 혹은 stack을 사용할 수도 있다.

3. FIFO(first in first out) : 가장 먼저 들어온 것을 교체. 오래된 것은 이미 모두 처리했을 것이라는 가정 하에 이루어지는 알고리즘. 그런데, 일반적으로 프로그램에서 코어와 로컬 부분이 존재할 때, 코어 부분은 프로그램의 시작부터 끝까지 모두 필요하므로 이들에 대해서는 계속 교체되는 경우가 있을 수도 있다. 그러나 circular buffer 등을 통해 쉽게 구현할 수 있고 간단하다.

4. clock(=second chance) : 상기한 방법의 문제점을 개선하기 위해 used bit을 추가하는 방법. 만약 어떤 페이지가 사용되었다면 used bit를 1이라 놓고, buffer를 돌며 오래된 것을 교체하려고 시도할 때는 0으로 바꾼다. 따라서 교체를 시도할 때 1이면 0으로 바꾸고 넘어가고, 0이면 바로 교체한다.
따라서 자주 사용되는 것들은 used bit가 계속 1과 0을 왔다갔다하며 교체되지 않지만, 오래되었고, 동시에 자주 사용되지 않는 것은 1에서 0으로 되고, 그 다음에는 바로 교체되게 된다.

page buffering : FIFO는 가장 간단하지만 성능이 좋지 않다. 따라서 이를 조금이라도 개선하기 위해 가장 오래된 것을 바로 교체하지 않고 page buffer에 modified와 unmodified로 분류하여 잠깐 대기하도록 하는 방법을 사용할 수 있다.
이 경우, 오래되었어도 히트되었다면 빨리 교체될 것이고, 또한 modified들은 메인 메모리에 업데이트 할 때 한 번에 cluster 하여 더 효율적으로 할 수 있다.