운영체제와 정보기술의 원리

4 minute read

8장 가상 메모리

프로그램이 실행되려면 실행에 당장 필요한 부분이 메모리에 올라와 있어야 한다.

한정된 메모리 공간을 여러 프로그램이 나누어 사용하므로 어떤 프로그램에게 어느 정도의 메모리를 할당할지가 중요하다.

운영체제는 몇몇 프로그램들에게 집중적으로 메모리 할당 후 메모리 회수해서 다른 프로그램에게 집중적으로 할당한다.

또, 운영체제는 당장 수행할 부분만 메모리에 올려놓고 아닌 부분은 스왑 영역에 두었다가 필요해지면 교체하는 방식을 사용한다. 이는 메모리의 연장 공간을 프로그램이 받는 것이 되므로 프로그램은 물리적 메모리 크기에 대한 제약을 생각하지 않아도 되어 자신만의 메모리 주소 공간을 가정하고 가상메모리 라고 부른다.

요구 페이징

대부분 이 방식을 사용하며 모든 페이지를 올리는 것이 아니라 특정 페이지에 대해 CPU 요청이 들어온 후에야 페이지를 메모리에 올리는 것을 말한다.

메모리 사용량이 감소하고 프로세스 전체를 메모리에 올리는 데 소요되는 입출력 오버헤드도 줄어든다.

물리적 메모리 용량 제약을 벗어나 물리적 메모리보다 큰 프로그램도 실행할 수 있다.

유효-무효 비트 를 이용해 어떤 페이지가 존재하는지 표시한다.

유효는 메모리에 적재되어 있는 상태를 의미한다.

무효는 페이지가 속한 주소 영역을 사용하지 않는 경우와, 페이지가 메모리에 없는 경우가 있다. 필요한데 없는 경우 페이지 부재라고 한다.

요구 페이징 페이지 부재 처리

MMU가 페이지 부재 트랩을 발생시킨다. 그럼 CPU의 제어권이 커널모드가 되고, 페이지 부재 처리루틴에 따라 처리한다.

  1. 운영체제의 접근이 올바른지 체크

    사용되지 않는 주소거나 접근 권한(읽기전용) 위반인 경우 프로세스 종료

  2. 물리적 메모리에서 비어있는 프레임을 할당받아 페이지 소환

    비어 있는 프레임이 없다면 기존 메모리에 있는 페이지 하나 디스크로 스왑 아웃 (페이지 교체)

루틴은 오랜 시간이 소요돼 프로세스는 CPU를 빼앗기고 봉쇄 상태가 된다. 이 때, CPU 레지스터 상태, PC값을 PCB에 저장해둔다.

입출력 완료되어 인터럽트 발생하면 봉쇄됐던 프로세스를 준비 큐로 옮기고 할당받으면 불러와서 재시작한다.

요구 페이징 성능

페이지 부재가 발생하면 요청된 페이지를 디스크로부터 읽어오는 데에 막대한 오버헤드가 발생해 성능이 가장 크다.

요구 페이징의 성능은 페이지를 참조하는 데 걸리는 유효 접근시간으로 측정한다.

  • 유효 접근 시간 = (1-P) * 메모리 접근시간 + P * 오버헤드 시간


페이지 교체

페이지 부재가 발생했는데 빈 프레임이 없을 때 하나의 페이지를 골라 스왑 아웃하는 것으로 이 때 어떤 페이지를 쫓아낼지는 교체 알고리즘을 이용한다.

페이지 참조열에 대해 페이지 부재율을 계산함으로써 이 알고리즘의 성능을 측정할 수 있다.

최적 페이지 교체

물리적 메모리에 존재하는 메모리 중 가장 먼 미래에 참조될 페이지를 쫓는다.

하지만 어떤 순서로 참조될지 미리 알고 있어야 하므로 실제 시스템에서 사용할 수 있는 알고리즘이 아니다.

image

선입선출 알고리즘 FIFO

메모리에 올라온 순서대로 내쫓는다. 엄청 비효율적인 상황이 발생할 수 있다.

예를 들어, 메모리 공간이 늘어났음에도 오히려 성능이 나빠지는 경우가 생기는데 이를 FIFO의 이상 현상이라고 한다.

image

LRU(Least Recently Used)

가장 최근에 사용된 페이지가 추후에 먼저 사용될 것이라는 가정 하에 가장 오래 전에 참조된 페이지를 내쫓는다.

image

701 후에 2가 없으니 넣어야 하는데 가장 오래전에 사용한게 7이므로 7 OUT

LFU(Least Frequently Used)

가장 많이 참조된 페이지가 추후에도 많이 참조될 것이라는 가정 하에 가장 적게 참조된 페이지를 내쫓는다.

같은 횟수가 여러 개인 경우 임의로 하나를 골라 내쫓는다. 이 때 오래 전에 참조된 걸 내쫓는게 효율적이다.

오랜 시간 동안의 참조 기록 반영한다는 장점, 시간 반영이 안되고 구현이 복잡하다는 단점

  • Incache-LFU

    메모리에 올라온 후부터의 참조횟수 카운트

  • Perfect-LFU

    메모리 적재 여부에 관련 없이 과거 총 참조횟수 카운트

클럭(Clock)

하드웨어적인 자원을 이용해 LRU를 근사시킨 알고리즘으로 NRU(Not Recently Used)나 NUR(Not Used Recently)로도 불린다.

오랫동안 참조되지 않은 페이지 중 하나를 내쫓는다. 가장 오래전에 참조되었음을 보장하지 못한다.

참조비트를 순차적으로 조사하며 참조될 때 1로 세팅되고 시계 돌듯 돌면서 1인 페이지는 0으로, 0인 페이지는 교체하는 방식으로 진행한다.

시계가 한바퀴 돌았는데도 0이라는 것은 그동안 참조되지 않았다는 것을 의미하기 때문이다.

적어도 시곗바늘이 한 바퀴 도는 시간만큼 메모리를 살려두어서 2차 기회 알고리즘이라고도 한다.

대부분의 시스템에서 적용하는 알고리즘이다.

image


페이지 프레임의 할당

프로세스 여러 개가 동시에 수행되는 상황에서 얼마만큼의 메모리 공간을 할당할지 결정하는 알고리즘

  • 균등할당

    모든 프로세스에게 페이지 프레임을 균일하게 할당

  • 비례할당

    프로세스의 크기에 비례해 프레임 할당

  • 우선순위할당

    우선순위에 따라 프레임을 다르게 할당, 당장 실행될 프로세스와 아닐 프로세스 나누어 할당

현재 수행 중인 프로세스가 너무 많으면 할당되는 메모리 양이 적어져 알고리즘만으로는 제대로 할당할 수 없다.

이 때는 적어도 일정 수준 이상의 페이지 프레임을 각 프로세스에 할당해야 한다. 반복문 실행 중일 경우 페이지를 모두 메모리에 올리는 것이다.

뿐만 아니라 시간에 따라 필요한 메모리 양이 달라질 수 있는 상황을 고려해 결정해야 한다.


전역교체와 지역교체

교체 대상이 될 프레임의 범위를 어떻게 정할지 구분하는 것

  • 전역교체

    모든 페이지 프레임이 교체 대상이 되는 것

    전체 메모리를 각 프로세스가 공유하고 교체 알고리즘에 의해 할당되는 메모리 양이 가변적으로 변하는 것

    LRU, LFU, CLOCK, 킹셋, PFF

  • 지역교체

    현재 수행 중인 프로세스에게 할당된 프레임 내에서만 교체 대상이 되는 것

    프로세스마다 페이지 프레임을 미리 할당하는 것


스레싱

프로세스가 원활하게 수행되기 위해서는 일정 수준 이상의 페이지 프레임을 받아야 한다. 그렇지 않으면 페이지 부재율이 크게 상승해 CPU 이용률이 급격히 떨어지는 스레싱이 일어난다.

CPU 이용률이 낮을 경우 메모리에 올라와 있는 프로세스의 수가 적기 때문이라고 OS는 판단한다. 준비큐가 비는 것이다. 따라서 OS는 메모리에 올라가는 프로세스의 수(Multi-Programming Degree)를 늘리게 된다.

MPD가 너무 높아지면 각 프로세스에 할당되는 메모리 양이 지나치게 감소한다. 그럼 각 프로세스는 페이지 부재가 빈번해지고 디스트 I/O가 일어나 다른 프로세스로 넘어가는데 또 메모리 적어 페이지 부재 -> 다른 CPU 이양이 반복되고 MPD를 높이기 위해 또 다른 프로세스를 올리게 되고 악순환이 계속된다.

최종적으로 프로세스들은 서로의 페이지를 교체하면서 스왑 인과 아웃을 지속적으로 발생시키고 CPU는 일을 하지 않는다. 이것이 스레싱이다.

이를 방지하고 MPD를 적절히 조절해 CPU 이용률을 높이기 위해 워킹셋 알고리즘과 페이지 부재 빈도 알고리즘을 사용한다.

워킹셋(working-set)

프로세스는 일정 시간동안 특정 주소 영역을 집중적으로 참조하는 경향이 있다.

이 때 집중적으로 참조되는 페이지들의 집합은 지역성 집합 이라고 한다.

워킹셋은 원활한 수행을 위해 한꺼번에 올라와 있어야 하는 페이지 집합을 워킹셋이라고 하고 이 워킹셋이 올라갈 수 있는 경우에만 프로세스에 메모리를 할당한다.

전부 올라갈 수 없는 경우 프레임을 모두 반납하고 주소 공간 전체를 디스크로 스왑 아웃한다.

  • 워킹셋을 구하는 방법

    워킹셋 윈도우를 사용한다. 일정 시간동안 사용된 페이지들은 메모리에 유지되고 아니면 쫓겨난다.

    윈도우 크기가 너무 작으면 지역성 집합을 모두 수용하지 못하고, 너무 크면 MPD가 감소해 CPU 이용률이 낮아질 수 있다. 이를 잘 결정해야 한다.

    워킹셋 크기가 프레임 수보다 클 경우 일부 프로세스를 스왑 아웃시켜 전부 올라가도록 보장한다. MPD가 줄어드는 효과가 있다.

워킹셋 알고리즘은 많이 필요할 땐 많이, 적게 필요할 땐 적게 할당하는 일종의 동적 프레임 할당 기능까지 수행한다.

image

페이지 부재 빈도 알고리즘

페이지 부재율을 주기적으로 조사하고 이에 따라 각 프로세스에 할당할 메모리 양을 동적으로 조절한다.

페이지 부재율이 상한값을 넘으면 프레임을 추가 할당한다. 빈 프레임 없으면 프로세스 스왑 아웃시킨다.

페이지 부재율이 하한값보다 떨어지면 프레임 수를 줄인다. 모든 프로세스에 필요한 프레임 다 할당했으면 스왑 아웃됐던 프로세스에 프레임할당해 MPD 높인다.