티스토리 뷰
Virtual Memory Management (가상 메모리 관리)
가상 메모리란 메모리 내에 완전히 존재하지 않는 프로세스를 실행하는 기술을 의미한다. 프로그램의 인스트럭션들은 실행되기 위해서 메모리에 로드되어야 하지만, 프로그램 전체가 필요한 것은 아니다. 만약 그렇다 하더라도, 동시에 프로그램 전체를 사용하지는 않는다. 즉, 프로그램이 CPU에 의해 실제로 사용되는 부분만 메모리로 로드하고, 사용되지 않는 부분은 디스크로 옮겨서 실제 메모리를 대체하도록 하는 것이다.
프로그램의 일부만 메모리로 로드하여 실행하는 것은 다음과 같은 장점이 있다.
- 물리 메모리의 크기에 제한받지 않는다.
- 더 많은 프로그램이 동시에 실행될 수 있다. (CPU utilization 증가)
- 페이지 테이블 전체를 읽을 필요가 없기 때문에 프로그램을 Load/Swap 하기 위한 I/O 연산이 줄어든다.
Demand Paging (요구 페이징)
요구 페이징이란 프로세스를 구성하는 페이지 전체를 메모리로 적재하는 것이 아니라, 당장 필요한 페이지만 메모리에 적재하는 기술이다. 프로세스 내에서 한 번도 접근되지 않은 페이지는 절대로 메모리에 로드되지 않는다.
요구 페이징의 기본적인 개념으로 디스크의 페이지를 메모리로 적재할 때, Pager는 어떤 페이지가 사용될지 예측하고 메모리로 적재시킨다. 이때, 이미 메모리에 적재되어있는 페이지와 디스크에 있는 페이지를 구분해야 한다. 이를 위해서 valid-invalid bit를 사용한다.
위의 그림에서 프로세스는 A~H를 다 쓴다고 생각하지만, 실제로 메모리에는 A, C, F만 로드되어 있다. 이때 페이지 테이블에 존재하지 않는 페이지에 프로세스가 접근하게 된다면 디스크에서 해당하는 페이지를 메모리로 로드하고, 페이지 테이블을 업데이트한다.
Page Fault (페이지 부재)
페이지 부재는 프로세스가 메모리에 존재하지 않는 페이지에 접근하려고 할 때 발생한다.
Copy-on-Write (COW)
fork() system call을 사용하면 자식 프로세스는 부모 프로세스를 복제한다. 즉, 프로세스를 복제하므로 부모와 자식 프로세스에 해당하는 메모리 내의 페이지 또한 중복된다. 게다가 fork() system call을 사용하면 대부분 exec() system call을 호출하기 때문에, 자식 프로세스는 제거되고 중복된 페이지 또한 메모리에서 해제되는데, 이는 운영체제 관점에서 매우 낭비적인 행위이다.
COW(Copy-on-Write)는 이러한 페이지의 불필요한 중복을 줄이는 방법이다. fork()를 통해 부모 프로세스가 소유하고 있던 메모리 영역은 모두 'copy-on-write'로 표시가 된다. 만약 자식 프로세스가 공유된 부모 프로세스의 페이지들 중 어떤 페이지라도 수정을 한다면 그때 페이지를 복사하여 수정한 후, 수정된 페이지를 메모리에 따로 저장한다.
COW의 장점은 자식 프로세스가 메모리에 로드된 페이지를 수정할 때에만 복사하기 때문에 기존의 fork()를 사용하여 페이지 전체를 복사할 때보다 빠르다.
Page Replacement (페이지 교체)
멀티 프로그래밍의 degree를 증가시키기 위해 프로세스를 계속 실행하다보면 Page over-allocation이 발생한다. 예를 들어 메모리에 프레임이 20개 있고, 한 개의 프로세스당 5개의 페이지가 필요하다면 총 4개의 프로세스가 동작할 수 있다. 하지만 어떤 프로세스가 추가적인 페이지가 필요하게 되면 Page Fault가 발생하고, 이를 해결하기 위해 디스크로부터 적절한 페이지를 찾아서 메모리로 적재시키려고 한다. 하지만 이 때 메모리에 남는 공간이 없으므로 이에 대한 해결책이 필요하다.
기본적인 Page Replacement (페이지 교체)
기본적인 페이지 교체 방식은 메모리 내에서 교체될 victim 페이지를 선택하여 swap-out하고, 사용할 페이지를 디스크로부터 swap-in 한다. 이 때 페이지 테이블 내의 valid-invalid 비트를 사용한다. 하지만 이는 swap-in & swap-out을 위해 디스크에 2번 접근해야하기 때문에 매우 느리다. 따라서 우리는 modify-bit를 사용한다.
Modify-bit는 하드웨어적으로 구현하며, 해당 페이지가 최근에 변경된 적이 있으면 1로 설정하고, 변경된 적이 없으면 0으로 설정한다. Swap-out을 수행하면서 만약 해당 페이지의 modify-bit가 0이라면(= 최근에 사용된 적이 없다면) 그대로 버리고, 1이라면 disk에 저장한다. 이와 같이 Modify-bit를 사용한 방법은 I/O 연산을 절반정도 줄일 수 있다.
Page Replacement는 적을수록 좋다. 왜냐하면 디스크와 관련된 I/O 연산이 줄어들기 때문에 응답시간이 더 짧아지기 때문이다.
FIFO Page Replacement
FIFO 페이지 교체는 가장 간단한 페이지 교체 알고리즘이며, 메모리 내에서 가장 오래된 페이지를 victim으로 선택하여 교체하는 방법이다. 항상 최적의 결과를 가져다주진 않지만, 동작은 올바르게 한다는 것이 보장된다.
메모리 내의 프레임의 갯수가 증가할 수록 Page Fault가 줄어드는 것이 이상적이지만, FIFO 페이지 교체에서는 프레임의 갯수가 늘어남에도 불구하고 Page Fault가 증가하는 경우가 존재한다. 이를 Belady's anomaly라고 한다.
Optimal Page Replacement
Optimal 페이지 교체는 가장 오랫동안 사용되지 않을 페이지를 교체하는 방법이다. Page Fault가 가장 적다는 것이 보장되며 Belady's anomaly도 일어나지 않는다. 하지만 미래의 페이지에 대한 정보가 필요하기 때문에 실제로 구현하기는 어렵다. (프로세스 스케줄링의 SJF와 비슷하다)
LRU Page Replacement (LRU: Least Recently Used)
Optimal 페이지 교체가 실제로 구현하기 어렵기 때문에 우리는 Optimal 페이지 교체 알고리즘의 Approximation을 사용한다. 과거의 정보를 사용하여 미래의 대한 정보를 추정한다. 즉, LRU 페이지 교체는 최근에 사용한 페이지 중에서 가장 오래된 페이지를 victim으로 선택하는 방법이다.
LRU 페이지 교체를 구현하기 위해 하드웨어를 사용한 다음의 두 가지 방법이 있다.
- Counter
- CPU에 클럭 레지스터를 추가한다. 이 레지스터는 메모리에 엑세스 할 때마다 증가한다.
- 페이지를 참조할 때마다 클럭 레지스터의 값이 페이지 테이블의 'time-of-use' 필드에 저장된다. 이렇게 함으로써 우리는 레지스터의 값을 통해 가장 최근에 페이지를 참조한 시간을 알 수 있다.
- 페이지 교체 시, 참조된 횟수가 가장 적은(time-of-use 값이 가장 작은) 페이지를 선택하여 교체한다.
- 단점
- 페이지 테이블 내의 모든 값을 비교해야 하기 때문에 full search에 대한 오버헤드가 발생한다.
- 페이지 테이블을 수정할 때 클럭 레지스터의 값이 유지되어야 한다.
- 클럭 레지스터에 대한 overflow를 고려해야 한다.
- Stack
- 페이지들을 관리할 스택을 사용하며, 이는 doubly-linked 리스트로 구현되어 있다.
- 스택의 바닥에 있는 페이지가 무조건 victim이다.
- 페이지가 참조될 때마다 스택에서 제거되고 다시 스택의 top으로 push된다. 따라서 가장 최근에 사용된 페이지는 스택의 top에 위치하게 된다.
- 단점
- 페이지를 참조할 때마다 스택 내 페이지들의 위치 이동에 대한 오버헤드가 존재한다.
Counting-based Page Replacement
Counting-based 페이지 교체는 페이지를 사용할 때마다 횟수를 기록하는 방법이다. 이 방법에는 다음과 같이 두 가지가 존재한다.
- LFU (Least Frequently Used)
- 카운트 값이 가장 작은 페이지를 victim으로 지정하고 교체하는 방법이다.
- 문제점
- 앞으로 많이 사용할 페이지가 들어오더라도, 적은 횟수를 가지고 있기때문에 victim이 될 수 있다.
- 초기에 많이 사용되고 더이상 사용하지 않을 페이지가 메모리에 남아있을 수 있다.
- MFU (Most Frequently Used)
- 가장 최근에 사용된 페이지는 카운팅 횟수가 적을 것이라는 판단 하에, 카운트 값이 가장 큰 페이지를 victim으로 지정하고 교체하는 방법이다.
LRU Approximation 알고리즘
위에서 우리는 counter와 stack을 사용한 LRU 페이지 교체를 살펴보았다. 하지만 현실에서는 이를 구현하기 위해 완벽하게 하드웨어를 지원하는 시스템은 거의 존재하지 않는다. 따라서 우리는 reference-bit를 사용한다.
- Reference bit
- 페이지에 접근할 때마다 하드웨어에 의해서 설정된다.
- 운영체제에 의해 초기값은 모두 0으로 설정된다.
- 우리는 reference bit를 통하여 어떤 페이지가 참조되었는지 알 수 있지만, 참조된 순서는 알 수 없다.
Additional-Reference-Bits 알고리즘
Additional-Reference-Bits 알고리즘은 페이지 테이블의 페이지마다 8비트의 reference bit를 가지며, 특정 시간 간격마다 reference bit의 값을 기록한다. Reference bit의 값을 기록할 때는 기존의 값을 right shift 하고, MSB에 reference bit의 값을 기록한다. 이 비트값을 사용하여 페이지를 사용한 시간으로 해석할 수 있으며, 비트값이 가장 작은 페이지가 victim이 된다. 하지만 단점으로는 가장 작은 비트값이 두 개 이상 존재할 수도 있다.
Second-Chance 알고리즘
Second-Chance 알고리즘은 이름 그대로 두 번의 기회를 주는 것이다. 기본적으로 reference bit가 0인 페이지를 victim으로 선택하며, reference bit가 1인 경우에는 0으로 설정하고 페이지에 접근한 시간을 업데이트한다. 그 후에 페이지를 교체하지 않고 다음 페이지부터 다시 탐색을 시작한다. 만약 모든 reference bit가 1인 경우에는 FIFO 페이지 교체와 같아진다.
Seconde-Chance 알고리즘은 주로 circular 큐를 사용하여 구현된다.
Enhanced Second-Chance 알고리즘
Enhanced Second-Chance 알고리즘은 reference bit만 고려하는게 아니라, modify bit도 추가하여 함께 고려한다. Reference bit는 페이지를 참조할 때 기록되는 반면, modify bit는 페이지의 내용을 수정할 때 기록된다. 우리는 페이지의 상태를 알기 위해 이 두 개의 비트를 가지고 다음과 같이 페이지 상태를 나타낼 수 있다.
- (Reference bit, Modify bit)
- (0, 0): Second-Chance 알고리즘을 통해 참조한 지 오래되었지만, 값이 수정된 적이 없음 (BEST)
- (0, 1): Second-Chance 알고리즘을 통해 참조한 지 오래되었지만, 값이 수정되었음
- (1, 0): 최근에 참조되었으며, 값이 수정된 적이 없음
- (1, 1): 최근에 참조되었으며, 값이 수정되었음
Enhanced Second-Chance 알고리즘은 위의 값들 중에서, 가장 낮은 값을 victim으로 선택하며, 최대 3번의 순회를 통해 victim을 구할 수 있다. 방법은 다음과 같다.
- 상태가 (0, 0)인 페이지를 찾아서 교체한다.
- 첫 번째 순회에서 victim 페이지를 찾지 못했다면 상태가 (0, 0)과 (0, 1)인 페이지를 찾아서 교체한다. 순회하면서 reference bit는 모두 0으로 만든다.
- 두 번째 순회에서 victim 페이지를 찾지 못했다면 페이지의 상태는 모두 (0, 0) 또는 (0, 1)만 남게된다. 그럼 다시 상태가 (0, 0)인 페이지를 찾아서 교체한다.
위와 같은 방법으로 victim 페이지를 찾으면 적어도 세 번째 순회가 끝날 때에는 모든 페이지의 상태가 (0, 0)이 되므로 victim을 찾을 수 있다.
Thrashing (쓰레싱)
우리는 프로세스에게 메모리 공간을 할당할 때 다음과 같은 이슈가 있다.
- 시스템이 요구하는 최소의 프레임
- 프로세스에게 메모리를 할당하는 방법 (균등하게 vs 상대적으로 다르게)
- Global replacement vs. Local replacement
- Global replacement: victim을 찾을 때 메모리 전체에서 찾겠다.
- Local replacement: victim을 찾을 때 해당 프로세스가 소유한 프레임 중에서 찾겠다.
만약 프로세스를 실행하기 위한 충분한 프레임을 지속적으로 확보하지 못한다면 Page Fault는 급격하게 증가할 것이고, 이를 Thrashing이라 한다. Thrashing을 일으키는 시나리오는 다음과 같다.
- 멀티프로그래밍의 degree를 증가시킨다.
- 한 개의 프로그램이 추가적인 프레임을 요구하고, 이를 해결하기 위해 전역적으로 페이지를 교체한다.
- 다른 프로그램 또한 추가적인 프레임을 요구하게 되고, Page Fault가 발생한다.
- Page Fault가 증가함에따라 디스크 I/O 작업이 증가하기 때문에 CPU utilization이 감소한다.
- CPU 스케줄러는 CPU utilization이 감소하였기 때문에, 이를 보완하기 위해 다시 멀티프로그래밍의 degree를 증가시킨다.
'컴퓨터공학 > 운영체제' 카테고리의 다른 글
| [운영체제] 메모리 관리 (2) (0) | 2020.01.24 |
|---|---|
| [운영체제] 메모리 관리 (1) (0) | 2020.01.21 |
| [운영체제] 동기화 (2) (0) | 2020.01.14 |
| [운영체제] 동기화 (1) (0) | 2020.01.10 |
| [운영체제] 데드락 (0) | 2019.10.30 |
- Total
- Today
- Yesterday