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

operating-system-study에서 스터디를 진행하고 있습니다.

다양한 캐싱 환경

• 캐싱 기법
  • 한정된 빠른 공간(=캐시)에 요청된 데이터를 저장해 두었다가 후속 요청시 캐시로부터 직접 서비스하는 방식이다.
  • 페이징 시스템 외에도 캐시 메모리, 버퍼 캐싱, 웹 캐싱 등 다양한 분야에서 사용한다.
• 캐시 운영의 시간 제약
  • 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 거리는 경우 실제 시스템에서 사용할 수 없다.
  • 버퍼 캐싱이나 웹 캐싱의 경우 O(1)에서 O(log N)까지 허용한다.
  • 페이징 시스템의 경우
    • 페이지 부재의 경우에만 OS가 관여한다.
    • 페이지가 이미 메모리에 존재하는 경우 참조 시각 등의 정보를 OS가 알 수 없다.
    • O(1)인 LRU의 List 조작조차 불가능하다.

 

페이징 시스템에서 LRU, LFU가 가능한가?

• 프로세스 A가 CPU를 잡고 실행 중인 상태이다. 따라서 프로세스 A의 논리적 메모리에서 매 순간 명령어를 읽어와서 수행을 할 것이다.
• 이때 논리적 주소를 페이지 테이블을 통해서 물리적 주소로 변환을 하여 물리적 메모리에 있는 내용을 CPU로 읽어와야 한다.
  • 만약, 주소 변환을 했는데 해당하는 페이지가 이미 물리적 메모리에 올라와 있다면 물리적 메모리를 그대로 읽으면 된다.
  • 이러한 주소 변환 과정은 모두 하드웨어가 담당하며, OS는 관여하지 않는다.
• 만약, 변환하려는 논리적 메모리의 유효-무효 비트의 값이 invalid이어서 페이지 부재가 발생하였다면 디스크 접근을 필요로 한다. 이때 I/O를 수행해야 하므로 trap이 발생하여 CPU의 제어권이 프로세스 A에서 OS로 넘어가게 된다.
• OS가 디스크의 페이지 부재가 발생한 페이지를 물리적 메모리로 올리고, 그 과정에서 물리적 메모리의 페이지 하나를 쫓아내야 한다. (물론 물리적 메모리의 빈 프레임이 있다면 바로 그 자리에 페이지를 올리면 된다.)
• 위 일련의 과정을 수행하면서 LRU, LFU 알고리즘을 적용할 수 있을까?
  • 프로세스가 요청한 페이지가 메모리에 이미 올라와 있는 경우에는 CPU가 OS로 넘어가지 않는다.
  • 페이지 부재가 발생해야 CPU 제어권이 OS로 넘어가므로 디스크에서 메모리로 페이지가 넘어오는 시간을 파악할 수 있다.
  • 정리하자면, 페이지 부재가 발생할 때만 페이지에 접근하는 정보를 알 수 있으므로 LRU, LFU 알고리즘은 페이징 시스템에서 사용할 수 없다. (버퍼 캐싱, 웹 캐싱은 가능)

 

클럭 알고리즘 (Clock Algorithm)

개념 및 특징

• LRU의 근사 알고리즘이다.
• Second chance algorithm, NUR(Not Used Recently), NRU (Not Recently Used) 등으로 불린다.
• 참조 비트를 사용하여 교체 대상 페이지를 선정한다. (circular list)
  • 참조 비트를 수정하는 작업은 OS가 아닌, 하드웨어가 수행한다.
  • 참조 비트가 0인 것을 찾을 때까지 포인터를 하나씩 앞으로 이동한다.

 

개선

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

 

동작 과정

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

 

페이지 프레임의 할당

• 각 프로세스에 얼마 만큼의 페이지 프레임을 할당할 것인가?
• 페이지 프레임 할당의 필요성
  • CPU에서 일반적으로 명령을 실행할 때는 여러 페이지를 동시에 참조하게 된다.
    • 프로세스의 주소 공간 중 코드, 데이터, 스택 등 각기 다른 영역을 참조하기 때문.
  • Loop를 구성하는 페이지들은 한꺼번에 프로세스에 할당되는 것이 유리하다.
    • 최소한의 페이지 할당이 없으면 매 반복문마다 페이지 부재가 발생한다.
• 페이지 프레임 할당 알고리즘
  • 균등 할당(Equal Allocation): 모든 프로세스에게 페이지 프레임을 균일하게 할당
  • 비례 할당(Proportional Allocation): 프로세스의 크기에 따라 페이지 프레임을 비례하여 할당
  • 우선순위 할당(Priority Allocation): 프로세스의 우선순위에 따라 페이지 프레임을 할당
    • 당장 CPU에서 실행될 프로세스와 그렇지 않은 프로세스를 구분

 

전역 교체와 지역 교체

전역 교체

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

 

지역 교체

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

 

스레싱

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

 

 

워킹셋 (Working-Set) 알고리즘

워킹셋 모델 (Working-Set Model)

• 참조의 지역성
  • 프로세스는 특정 시간동안 일정 장소만을 집중적으로 참조한다.
  • 집중적으로 참조되는 해당 페이지의 집합을 지역셋(locality set)이라고 한다.
• 워킹셋 모델
  • 지역성에 기반하여 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 페이지의 집합을 워킹셋이라고 정의한다.
  • 워킹셋 모델에서는 프로세스의 워킹셋 전체가 메모리에 올라와 있어야 수행되고, 그렇지 않을 경우 모든 페이지 프레임을 반납 한 후 swap out한다. 해당 프로세스는 suspend 상태가 된다.
    • 만약 워킹셋이 5개인데 페이지 프레임을 공간에 3개 밖에 없다면, 해당 프로세스는 모든 페이지 프레임을 반납하고 디스크로 쫓겨 난다.
  • MPD를 조절하여 스레싱을 방지한다.

 

워킹셋 알고리즘

• 워킹셋의 결정
  • 워킹셋 윈도우를 통해 알아낸다.
  • 윈도우 사이즈가 Δ인 경우
    • 시각 Ti에서의 워킹셋 WS(Ti)
      • Time interval [Ti - Δ, Ti] 사이에 참조된 서로 다른 페이지들의 집합
    • 워킹셋에 속한 페이지는 메모리에 유지하고, 속하지 않은 것은 메모리에서 쫓아낸다. 즉, 참조된 후 Δ 시간동안 해당 페이지를 메모리에 유지한 후 쫓아 냄.
• 알고리즘 동작 과정
  • 프로세스의 워킹셋 사이즈의 합이 페이지의 프레임 수보다 큰 경우
    • 일부 프로세스를 swap out한 뒤, 남은 프로세스의 워킹셋을 우선적으로 충족하여 MPD를 줄인다.
  • 워킹셋을 다 할당하고도 페이지 프레임이 남는 경우
    • swap out되었던 프로세스에게 워킹셋을 할당하여 MPD를 높인다.
• 윈도우 사이즈 Δ
  • 워킹셋을 제대로 탐지하기 위해서는 윈도우 사이즈를 잘 결정해야 한다.
  • Δ 값이 너무 작으면 지역셋을 모두 수용하지 못할 수 있다.
  • Δ 값이 너무 크면 여러 규모의 지역셋을 수용할 수 있다.
  • Δ 값이 무한대이면 전체 프로그램을 구성하는 페이지를 워킹셋으로 간주한다.

 

워킹셋 알고리즘의 예제

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

 

PFF (Page-Fault Frequency) 알고리즘

• 페이지 부재 빈도 알고리즘은 프로세스의 페이지 부재율을 주기적으로 조사하고 이 값에 근거해서 각 프로세스에 할당할 메모리 양을 동적으로 조절한다.
• 페이지 부재율의 상한값과 하한값을 둔다.
  • 페이지 부재율의 상한값을 넘으면 페이지 프레임을 더 할당한다.
  • 페이지 부재율의 하한값보다 낮으면 할당 페이지 프레임 수를 줄인다.
• 빈 페이지 프레임이 없으면 일부 프로세스를 swap out한다.

 

 

페이지 사이즈의 결정

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

 

가상 메모리 관련 기타 정보

가상 메모리를 사용하는 이유

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

 

가상 메모리의 중요성

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

 

출처

• https://core.ewha.ac.kr/publicview/C0101020140513133424380501?vmode=f
• https://velog.io/@yuhyerin/kocw-운영체제-반효경-9.-Virtual-Memory2#8-working-set-algorithm
• 운영체제와 정보 기술의 원리 - 반효경