[OS] Virtual Memory - 2

본 글은 반효경 교수님의 운영체제 강의를 들으며 정리하는 글 입니다.

 

3. 다양한 캐싱 환경

▶ 캐싱 기법

• 한정된 빠른 공간(=캐시)에 요청된 데이터를 저장해 두었다가 후속 요청시 캐시로부터 직접 서비스하는 방식이다.
• 페이징 시스템 외에도 캐시 메모리, 버퍼 캐싱, 웹 캐싱 등 다양한 분야에서 사용한다.

 

▶ 캐시 운영의 시간 제약

• 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 거리는 경우 실제 시스템에서 사용할 수 없다.
• 버퍼 캐싱이나 웹 캐싱의 경우 O(1)에서 O(log N)까지 허용한다.
• 페이징 시스템의 경우
  • Page Fault의 경우에만 OS가 관여한다.
  • 페이지가 이미 메모리에 존재하는 경우 참조 시각 등의 정보를 OS가 알 수 없다. 즉 반쪽짜리 정보를 알게된다.
  • O(1)인 LRU의 List 조작조차 불가능하다.

 

3 - 1) 페이징 시스템에서 LRU, LFU가 적용 가능한가?

프로세스 A가 CPU를 잡고 실행 중인 상태이다. 따라서 프로세스 A의 논리적 메모리에서 매 순간 명령어를 읽어와서 수행을 할 것이다.

이때 논리적 주소를 페이지 테이블을 통해서 물리적 주소로 변환을 하여 물리적 메모리에 있는 내용을 CPU로 읽어와야 한다.

 

만약, 주소 변환을 했는데 해당하는 페이지가 이미 물리적 메모리에 올라와 있다면 물리적 메모리를 그대로 읽으면 된다.

이러한 주소 변환 과정은 모두 하드웨어가 담당하며, OS는 관여하지 않는다.

 

만약, 변환하려는 논리적 메모리의 유효-무효 비트의 값이 invalid이어서 Page Fault가 발생하였다면 디스크 접근을 필요로 한다.

이때 I/O를 수행해야 하므로 trap이 발생하여 CPU의 제어권이 프로세스 A에서 OS로 넘어가게 된다.

 

OS가 디스크의 page fault가 발생한 페이지를 물리적 메모리로 올리고, 그 과정에서 물리적 메모리의 페이지 하나를 쫓아내야 한다.

(물론 물리적 메모리의 빈 프레임이 있다면 바로 그 자리에 페이지를 올리면 된다.)

 

위 일련의 과정을 수행하면서 LRU, LFU 알고리즘을 적용할 수 있을까?

• 프로세스가 요청한 페이지가 메모리에 이미 올라와 있는 경우에는 CPU가 OS로 넘어가지 않는다.
• Page Fault가 발생해야만 CPU 제어권이 OS로 넘어가므로 디스크에서 메모리로 페이지가 넘어오는 시간을 파악할 수 있다.
• 정리하자면, Page Fault가 발생할 때만 페이지에 접근하는 정보를 알 수 있으므로 LRU, LFU 알고리즘은 페이징 시스템에서 사용할 수 없다. (버퍼 캐싱, 웹 캐싱은 가능)

 

4. 클럭 알고리즘 (Clock Algorithm)

4 - 1) 개념 및 특징

LRU의 근사 알고리즘이며, Second chance algorithm, NUR(Not Used Recently), NRU (Not Recently Used) 등으로 불린다.

참조 비트를 사용하여 교체 대상 페이지를 선정한다. (circular list)

• 참조 비트를 수정하는 작업은 OS가 아닌, 하드웨어가 수행한다.
• 참조 비트가 0인 것을 찾을 때까지 포인터를 하나씩 앞으로 이동한다.

 

4 - 2) 동작 과정

1. 각 사각형은 물리적 메모리에 있는 페이지 프레임을 뜻한다.
2. 페이지에 대해 어떤 페이지가 참조되어 CPU가 그 페이지를 사용하게 되면, 그 페이지에 reference bit가 1로 설정된다. (하드웨어가 하는 일)
3. OS는 포인터를 이동하면서 페이지의 reference bit가 이미 1이면, 페이지를 쫓아내지 않고 reference bit를 0으로 세팅한 후 다음 페이지의 reference bit를 검사한다.
4. OS는 다시 포인터를 이동하다가 reference bit가 0인 페이지를 찾으면, 해당 페이지를 쫓아낸다.
   • reference bit는 해당 페이지가 참조될 때 하드웨어가 1로 자동으로 세팅하므로 시계 바늘이 한 바퀴 돌아오는 동안에 다시 참조되지 않은 경우 그 페이지는 교체되는 것이다.
   • 즉, A라는 page frame의 참조 비트를 0으로 바꾼 후, 다시 한 바퀴 돌아서 A page frame의 참조 비트가 0이면 가장 오랫동안 참조가 일어나지 않은 페이지라고 판단하는 것이다.
   • 이는 LRU와 근사한 방식이다.
5. 개선 클럭 알고리즘은 reference bit 외에 modified bit를 사용한다.
   • modified bit는 어떤 페이지가 쫓겨날 때, 이 페이지의 수정 비트가 0이면 backing store에서 물리적 메모리로 올라온 이후로 수정이 되지 않은 페이지이므로 바로 메모리에서 지워도 된다.
   • 하지만 modified bit가 1이면 물리적 메모리로 올라온 이후로 상태의 수정이 일어난 페이지이므로 쫓겨나기 전에 backing store에 수정한 내용을 반영하고 메모리에서 지워야 한다.
   • 그래서 modified bit 가 1이면 디스크로 쫓겨나는 페이지의 수정된 내용을 반영하는 오버헤드가 발생한다. 따라서 해당 페이지를 쫓아내기 보다는, 그대로 둔다.

 

4 - 3) 개선

• 참조 비트와 수정 비트를 함께 사용한다.
• 참조 비트가 1이면 최근에 참조된 페이지이며, 수정 비트가 1이면 최근에 변경된 페이지를 뜻한다.

 

5. Page Frame의 Allocation

각 프로세스에 얼마 만큼의 페이지 프레임을 할당할 것인가? 가 중요하다.

 

페이지 프레임 할당의 필요성 : CPU에서 일반적으로 명령을 실행할 때는 여러 페이지를 동시에 참조하게 된다.

프로세스의 주소 공간 중 코드, 데이터, 스택 등 각기 다른 영역을 참조하기 때문이다.

 

예를 들어 Loop를 구성하는 페이지가 총 3개라면, 이 3개는 한꺼번에 프로세스에 할당되는 것이 유리하다.

for loop가 돈느 동안에는 이미 할당되 있는 3개의 페이지에서 바로 사용하는 것이 효율적이기 때문이다.

이런 경우 Loop를 구성하는 page들은 한번에 allocation되는 것 이 유리하다.

 

그러나 이런, 최소한의 페이지 할당이 없으면 매 반복문마다 page fault가 발생한다.

 

5 - 1) Page Frame Allocation 알고리즘

균등 할당(Equal Allocation): 모든 프로세스에게 페이지 프레임을 균일하게 할당

비례 할당(Proportional Allocation): 프로세스의 크기에 따라 페이지 프레임을 비례하여 할당

우선순위 할당(Priority Allocation): 프로세스의 우선순위에 따라 페이지 프레임을 할당

 

당장 CPU에서 실행될 프로세스와 그렇지 않은 프로세스를 구분

 

5 - 1) 전역 교체와 지역 교체

5 - 1 - 1) 전역 교체

• 모든 페이지 프레임이 교체 대상이 될 수 있는 방법이다.
• 전체 메모리를 각 프로세스가 공유해서 사용하고, 교체 알고리즘에 근거해서 할당되는 메모리 양이 가변적으로 변하는 방법이다.
  • 페이지 교체 시 다른 프로세스의 프레임을 빼앗아 올 수 있으므로 프로세스별 프레임 할당량을 조절할 수 있게 된다.
• FIFO, LRU, LFU 등의 알고리즘을 전역 교체로 사용할 수 있다.
• Working set, PFF 알고리즘을 전역 교체로 사용할 수 있다.

 

5 - 1 - 2) 지역 교체

• 자신에게 할당된 페이지 프레임 내에서만 교체한다.
• FIFO, LRU, LFU 등의 알고리즘을 지역 교체로 사용할 수 있다.

아무래도 자신에게 할당되있는 자원 안에서 효율적으로만 사용하면 되기 때문에 경쟁하지 않는다는 장점이 있다.

 

6. Thrashing

프로세스의 원활한 수행에 필요한 최소한 페이지 프레임 수를 할당 받지 못하면 page fault가 자주 발생하여 CPU 이용률이 떨어지는데, 이를 Thrasing이라고 한다.

 

스레싱이 발생하는 시나리오는 다음과 같다.

• OS는 CPU 이용률이 낮을 경우 메모리에 올라와 있는 프로세스의 수가 적다고 판단하여 메모리에 올라가는 프로세스를 늘린다. (CPU 이용률이 낮으면 MPD, multi programming degree를 높인다.)
  • 준비 큐에 프로세스가 단 하나라도 있으면 CPU는 그 프로세스를 실행하므로 쉬지 않고 일하게 되는데, CPU 이용률이 낮다는 것은 준비 큐가 비어있다는 것을 뜻한다.
  • 메모리에 동시에 올라가 있는 프로세스의 수를 다중 프로그래밍의 정도(MPD)라고 부른다.
• MPD가 과도하게 높아지면 각 프로세스에게 할당되는 메모리의 양이 지나치게 감소한다.
• 각 프로세스는 그들이 원활하게 수행되기 위해 필요한 최소한의 페이지 프레임도 할당 받지 못하므로 페이지 부재율이 급격히 증가한다.
• 페이지 부재가 발생하면 I/O 작업을 수반하므로 다른 프로세스에게 CPU가 넘어간다.
• 다른 프로세스 역시 페이지 부재가 발생하고 있어서 또 다른 프로세스에게 CPU가 넘어간다.
• 결국 준비 큐에 있는 모든 프로세스에게 CPU가 한 차례씩 할당 되었는데도 모든 프로세스가 다 페이지 부재를 발생하여 CPU의 이용률이 급격하게 떨어진다. 그저 I/O만 요청하고 끝나버린다.
• OS는 위 현상이 메모리에 MPD가 낮다고 판단하여 MPD를 높이려고 한다.
• 위 악순환이 계속 반복되는 상황을 스레싱이라고 부른다.

x축은 지금 메모리에 올라온 프로그램의 수, y축은 CPU 이용률 이다.

 

7. Working-Set 알고리즘

7 - 1) 워킹셋 모델 (Working-Set Model)

7 - 1 - 1) Locality of reference

Process는 특정 시간동안 일정 장소만을 집중적으로 참조한다.

집중적으로 참조되는 해당 페이지의 집합을 locality set이라고 한다.

 

7 - 1 - 2) Working-set 모델

Locality에 기반하여 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 page의 집합을 Working-Set이라고 정의한다.

 

working-set 모델에서는 프로세스의 working-set 전체가 메모리에 올라와 있어야 수행되고, 그렇지 않을 경우 모든 페이지 프레임을 반납 한 후 swap out한다. 이후 해당 프로세스는 suspend 상태가 된다.

 

만약 working-set이 5개의 프레임인데 페이지 프레임 공간에 빈곳이 3개 밖에 없다면, 해당 프로세스는 모든 페이지 프레임을 반납하고 디스크로 쫓겨 난다.

 

MPD를 조절하여 스레싱을 방지한다.

 

7 - 2) Working-set 알고리즘

7 - 2 - 1) working-set의 결정

• working-set window를 통해 알아낸다.
• window size가 Δ(델타)인 경우
  • 시각 Ti에서의 워킹셋 WS(Ti)
    • Time interval [Ti - Δ, Ti] 사이에 참조된 서로 다른 페이지들의 집합
  • 워킹셋에 속한 페이지는 메모리에 유지하고, 속하지 않은 것은 메모리에서 쫓아낸다.
  • 즉, 참조된 후 Δ 시간동안 해당 페이지를 메모리에 유지한 후 쫓아 낸다.

7 - 2 - 2) 알고리즘 동작 과정

프로세스의 working-set 사이즈의 합이 페이지의 프레임 수보다 큰 경우

• 일부 프로세스를 swap out한 뒤, 남은 프로세스의 워킹셋을 우선적으로 충족하여 MPD를 줄인다.

워킹셋을 다 할당하고도 페이지 프레임이 남는 경우

• swap out되었던 프로세스에게 워킹셋을 할당하여 MPD를 높인다.

윈도우 사이즈 Δ

• 워킹셋을 제대로 탐지하기 위해서는 윈도우 사이즈를 잘 결정해야 한다.
• Δ 값이 너무 작으면 지역셋을 모두 수용하지 못할 수 있다.
• Δ 값이 너무 크면 여러 규모의 지역셋을 수용할 수 있다.
• Δ 값이 무한대이면 전체 프로그램을 구성하는 페이지를 워킹셋으로 간주한다.

 

7 - 3) 워킹셋 알고리즘의 예제

• Δ(델타)는 10인 상태라고 가정한다.
• t1일 때 프로세스의 워킹셋은 5개의 페이지로 구성되는 반면, t2일 때 프로세스의 워킹셋은 2개의 페이지로 구성된다.
• 이처럼 프로세스가 메모리를 많이 필요로 할 때에는 많이 할당하고, 적게 필요로 할 때에는 적게 할당하는 동적인 프레임 할당 기능을 수행한다.

 

8. PFF (Page-Fault Frequency) 알고리즘

페이지 부재 빈도 알고리즘은 프로세스의 페이지 부재율을 주기적으로 조사하고 이 값에 근거해서 각 프로세스에 할당할 메모리 양을 동적으로 조절한다.

 

페이지 부재율의 상한값과 하한값을 둔다.

• 페이지 부재율의 상한값을 넘으면 페이지 프레임을 더 할당하여 page-fault비율을 줄인다.
• 페이지 부재율의 하한값보다 낮으면 할당 페이지 프레임 수를 줄인다. 낭비되는 페이지를 줄이는 것 이다.

빈 페이지 프레임이 없으면 일부 프로세스를 swap out한다.

 

9. 페이지 사이즈의 결정

• 페이지 사이즈를 감소하면 어떻게 될까?
  • 페이지 수 증가
  • 페이지 테이블 크기 증가
  • 내부 단편화 감소
  • Disk transfer의 효율성 감소
    • 한 번의 디스크 헤더 움직임으로 많은 양의 내용을 읽어오는 것이 좋은데, 페이지 사이즈가 적으면 그렇지 못한다.
  • 필요한 정보만 메모리에 올라와 메모리 이용이 효율적, 다만 지역성의 활용 측면에서는 좋지 않음
• 최근에는 페이지 사이즈를 크게 가져가는편이다.

 

10. 가상 메모리 관련 기타 정보

10 - 1) 가상 메모리를 사용하는 이유

• 메모리에 확장성을 부여한다.
  • 물리 메모리는 한정적이지만, 가상 메모리는 큰 공간으로 구성이 가능하다.
  • 가상 메모리를 사용하면 실제 메인 메모리 장치가 아닌, 디스크를 부가적인 메모리 공간으로 활용할 수 있다.
• 모든 프로그램에 동일한 메모리 공간을 제공해 줄 수 있다.
  • 개발자 입장에서 물리적 메모리가 아닌 OS가 제공하는 메모리 공간만 신경 쓰면 된다.
  • 운영 체제가 동작하는 환경에서는 여러 가지 프로그램이 동시에 실행되므로 메모리 공간에 대한 관리가 필요하다.
• 메모리 할당과 관리에 효율적이다.
  • 물리적으로 연속되지 않은 메모리라도 가상으로 연속적인 메모리 공간으로 사용이 가능하다.
• 메모리 보호 기능을 제공한다.
  • 보안이나 안정성 측면에서 매우 중요한 기능이다.
  • 각각의 프로세스는 별도의 메모리 공간을 점유하며, 다른 프로세스의 메모리 공간을 참조할 수 없다.

 

10 - 2) 가상 메모리의 중요성

• 가상 메모리는 메모리 사용량이 늘어남에 따라, 디스크의 일부를 마치 확장된 RAM처럼 사용할 수 있게 해 주는 기술이다.
• 커널은 실제 메모리에 올라와 있는 메모리 블록 중 당장 쓰이지 않는 것을 디스크에 저장하는데, 이를 통해 사용 가능한 메모리의 영역을 훨씬 늘릴 수 있게 된다. 디스크에 저장되어 있던 메모리 블록은 다시 필요하면 실제 메모리로 올려지며, 대신 다른 블록이 디스크로 내려가게 된다.
• 이러한 과정은 사용자에게 전혀 보이지 않고, 프로그램에게도 그저 많은 양의 메모리가 있는 것처럼 보일 뿐이어서 점유하고 있던 메모리가 디스크에 있는지 실제 메모리에 있는지 전혀 신경 쓸 필요가 없게 된다.
• 그러나, 하드 디스크를 읽고 쓰는 시간은 RAM보다 훨씬 느리기 때문에 프로그램의 실행은 그만큼 느려진다.
• 이때 가상 메모리로 쓰이는 하드 디스크의 영역을 스왑 영역(백킹스토어)라고 부른다.
• 메모리 스와핑은 두 가지 측면에서 중요하다.
  • 시스템에서 특정 애플리케이션이나 프로세스가 현재 가용한 물리 메모리보다 많은 양의 메모리를 요청할 수 있다. 이때 커널은 적은 빈도로 사용되는 메모리 페이지를 스왑 아웃해서 가용 메모리 공간을 확보한 뒤 이를 해당 프로세스에게 할당해 줌으로써 프로세스 실행이 가능하게 한다.
  • 애플리케이션이 실행되기 시작할 때 초기화를 위해서만 필요하고 이후에는 사용되지 않는 메모리 페이지들은 시스템에 의해 스왑 아웃된다. 이로 인해 가용 가능한 메모리 공간은 다른 애플리케이션이나 디스크 캐시 용도로 활용된다.

 

참고

https://core.ewha.ac.kr/publicview/C0101020140513133424380501?vmode=f 

반효경 [운영체제] 23. Virtual Memory 2

https://steady-coding.tistory.com/572

[반효경 운영체제] Virtual Memory 2