메모리 관리와 페이지 교체

메모리 관리

• 다중 프로그래밍 시스템에 여러 프로세스를 수용하기 위해 주기억장치를 동적 분할하는 메모리 관리 작업이 필요

메모리 관리 기법

1. 연속 메모리 관리
   • 프로그램 전체가 하나의 커다란 공간에 연속적으로 할당되어야 한다.
   • 고정 분할 기법: 주기억장치가 고정 파티션으로 분할 → 내부의 단편화 발생
   • 동적 분할 기법: 파티션들이 동적 생성 되어 자신의 크기와 같은 파티션에 적재 → 외부 단편화 발생
2. 불연속 메모리 관리
   • 프로그램의 일부가 서로 다른 주소 공간에 할당될 수 있는 기법
   • 페이지 : 고정 사이즈의 작은 프로세스 조각
   • 프레임 : 페이지 크기와 같은 주기억장치 메모리 조각
   • 단편화 : 기억 장치의 빈 공간 또는 자료가 여러 조각으로 나뉘는 현상
   • Pasging (페이징) : 고정 크기
     1. 단순 페이징
        • 각 프로세스는 프레임들과 같은 길이를 가진 균등 페이지로 나뉜다.
        • 외부 단편화 X, 내부 단편화만 소량 존재
     2. 가상 메모리 페이징
        • 단순 페이징과 비교하여 프로세스 페이지 전부를 로드시킬 필요는 없다.
        • 필요한 페이지만 나중에 자동으로 불러들여진다.
        • 외부 단편화X
        • 복잡한 메모리 관리로 오버헤드 발생
   • Segmentation (세그먼테이션) : 가변 크기
     1. 단순 세그먼테이션
        • 각 프로세스는 여러 세그먼트들로 나뉜다.
        • 내부 단편화X, 외부 단편화 존재
        • 메모리 사용 효율 개선, 동적 분할을 통한 오버헤드 감소
     2. 가상 메모리 세그먼테이션
        • 필요하지 않은 세그먼트들은 로드되지 않고 필요한 세그먼트가 있을 때 자동으로 불러들여진다.
        • 내부 단편화X
        • 복잡한 메모리 관리로 오버헤드 발생

 

 

메인 메모리

CPU가 직접 접근할 수 있는 기억장치, 프로세스가 실행되려면 프로그램이 메모리에 올라와야 한다.

주소가 할당된 일련의 바이트들로 구성되어 있음

 

MMU (Memory Management Unit)

CPU는 레지스터가 지시하는대로 메모리에 접근하여 다음에 수행할 명령어를 가져온다.

→ 명령어 수행 시 메모리에 필요한 데이터가 없다면 해당 데이터를 우선 가져와야 한다.

• 논리 주소를 물리 주소로 변환
• 메모리 보호나 캐시 관리 등 CPU가 메모리에 접근하는 것을 관리해주는 하드웨어

메모리 공간은 한정적이기에 사용자에게 더 많은 메모리를 제공하기 위해 ‘가상주소’라는 개념이 등장했고

이 가상 주소에서 실제 데이터가 담겨 있는 곳에 접근하기 위해선 빠른 주소 변환이 필요해졌고, 이를 MMU이 도와주는 것

*가상 주소는 프로그램 상에서 사용자가 보는 주소 공간

 

MMU의 역할

• MMU이 지원되지 않으면 Physical address를 직접 접근해야 하므로 부담이 생긴다.
• MMU은 사용자가 기억장소를 일일이 할당해줘야 하는 불편을 없애준다.
• 프로세스의 크기가 실제 메모리의 용량을 초과해도 실행할 수 있게 해준다.

메인 메모리의 직접 접근은 비효율적이므로 CPU와 메인 메모리 속도를 맞추기 위해 캐시가 존재한다.

 

MMU의 메모리 보호

프로세스는 독립적인 메모리 공간을 가져야 하고 자신의 공간만 접근해야 하므로 프로세스에 합법적인 주소 영역을 설정하여 잘못된 접근이 오면 trap을 발생시키며 보호한다.

1. base와 limit 레지스터를 활용한 메모리 보호 기법

• base 레지스터는 메모리상의 프로세스 시작 주소를 물리 주소로 저장
• limit 레지스터는 프로세스의 사이즈를 저장
• 프로세스의 접근 가능한 합법적인 메모리 영역 x는 base ≤ x < base+limit 이고, 이 영역 밖에서 접근을 요하면 trap을 발생시키는 것이다.
• 사용자 모드에선 직접 변경할 수 없이, 안정성을 위해 limit과 base는 커널 모드에서만 수정 가능하도록 설계한다.

 

 

메모리 과할당(over allocating)

실제 메모리의 사이즈보다 더 큰 사이즈의 메모리를 프로세스에 할당한 상황

• 페이지 기법과 같은 메모리 관리 기법은 사용자가 눈치 못 채도록 가상 메모리를 이용하여 눈속임으로 메모리를 할당해주는 것인데, 과할당 상황에 대해서 사용자를 속인 것을 들킬만한 상황이 존재한다.
  • 프로세스 실행 도중 페이지 폴트 발생
  • 페이지 폴트를 발생시킨 페이지 위치를 디스크에서 찾는다
  • 메모리의 빈 프레임에 페이지를 올려야 하는데 모든 메모리가 사용 중이라 빈 프레임이 없다
• 메모리 과할당을 해결하기 위해선 빈 프레임을 확보할 수 있어야 한다.
  1. 메모리에 올라와 있는 한 프로세스를 종료시켜 빈 프레임을 얻음
  2. 프로세스를 하나 swap out하고 이 공간을 빈 프레임으로 활용 (페이지 교체)
     • swapping 기법을 통해 공간을 바꿔치기 하는 2번 방법을 지향, 1번 방법은 페이징 시스템을 들킬 가능성이 매우 높아서 지양 ← 페이징 기법은 사용자 모르게 시스템 능률을 높이기 위해 선택한 일이므로 들키지 않게 처리해야 한다.

 

페이지 교체

메모리 과할당이 발생했을 때 프로세스 하나를 SWAP OUT해서 빈 프레임을 확보하는 것

• 페이지 교체가 이루어지면 아무일이 없었던 것처럼 프로세스를 계속 수행시켜주면서 사용자가 알지 못하도록 해야한다. 페이지 교체 당시 오버헤드를 최대한 줄여줘야 한다.

1. 프로세스 실행 도중 페이지 부재가 발생
2. 페이지 폴트를 발생시킨 페이지 위치를 디스크에서 찾음
3. 메모리에 빈 프레임이 있는지 확인
   • 빈 프레임이 있다면 해당 프레임을 사용,
   • 빈 프레임이 없다면 victim프레임을 선정하여 디스크에 기록하고 페이지 테이블을 업데이트 한다.
4. 빈 프레임에 페이지 폴트가 발생한 페이지를 올리고 페이지 테이블 업데이트

• 빈 프레임이 없을 때 victim프레임을 비울 때와 원하는 페이지를 프레임으로 올릴 때 2번의 디스크 접근이 이루어진다. 페이지 교체가 많이 이루어지면 입출력 연산이 많이 발생하면서 오버헤드 문제가 발생하므로 페이지 교체를 최대한 줄여주는 것이 오버헤드를 줄여주는 방법이다.

 

오버헤드를 감소시키는 방법

1. 변경 비트를 모든 페이지마다 두어, victim페이지가 정해지면 해당 페이지의 비트를 확인한다.
   • 해당 비트가 set 상태면 해당 페이지 내용이 디스크 상의 페이지 내용과 달라졌다는 의미로 페이지가 메모리에 올라온 이후 한번이라도 수정이 일어났던 것 → 디스크에 기록이 필요
   • clear 상태라면 디스크 상의 페이지 내용과 메모리 상의 페이지가 정확히 일치하는 상황 → 디스크에 기록할 필요 없음
   • 비트를 활용하여 디스크에 기록하는 횟수를 줄이면서 오버헤드에 대한 수를 최대한 절반으로 감소시키는 방법
2. 페이지 교체 알고리즘 사용
   • 페이지 폴트가 발생활 확률을 최대한 줄여줄 수 있는 교체 알고리즘 선택 → FIFO / OPT / LRU

 

페이지 교체 알고리즘

페이지 부재 발생 → 새로운 페이지를 할당해야 함 → 현재 할당된 페이지 중 어떤 것을 교체할 지 결정하는 방법

 

가상메모리는 요구 페이지 기법을 통해 필요한 페이지만 메모리에 적재하고 사용하지 않는 부분은 그대로 둔다. 하지만 필요한 페이지만 올려도 메모리는 결국 가득 차게 되고 올라와있던 페이지가 사용이 다 된 후에도 자리만 차지하고 있을 수 있다. 따라서 메모리가 가득 차면 추가로 페이지를 가져오기 위해 안쓰는 페이지는 out하고 해당 공간에 현재 필요한 페이지를 in 시켜야 한다.

out되는 페이지를 victim page(가장 먼저 메모리에 올라온 페이지)라고 부르며 수정이 되지 않는 페이지를 선택해야 한다. 만약 수정되면 메인 메모리에서 내보낼 때 하드디스크에서 또 수정을 진행해야 하므로 시간이 오래 걸리며 이를 위해 상황에 맞는 페이지 교체를 진행하기 위해 페이지 교체 알고리즘이 존재하는 것이다.

Page Reference String

CPU는 논리 주소를 통해 특정 주소를 요구하고 메인 메모리에 올라와 있는 주소들은 페이지 단위로 가져오기 때문에 페이지 번호가 연속되어 나타나게 되면 페이지 결함이 발생하지 않는다.

따라서 CPU의 주소 요구에 따라 페이지 결합이 일어나지 않는 부분은 생략하여 표시하는 방법

1. FIFO(First in First out) 알고리즘
   • 메모리에 먼저 올라온 페이지를 먼저 내보내는 알고리즘
   • 가장 간단한 방법으로 특히 초기화 코드에 적절한 방법이다.
     • 초기화 코드는 처음 프로세스가 실행될 때 최초 초기화를 시키는 역할만 진행하고 다른 역할은 수행하지 않으므로 메인 메모리에서 빼도 된다.
     • 다만 처음 프로세스 실행 시 무조건 필요한 코드이므로 FIFO 알고리즘을 사용하면 초기화를 시켜준 후 가장 먼저 내보내는 것이 가능하다.
2. OPT(Optimal Page Replacement) 알고리즘
   • 앞으로 가장 사용되지 않을 페이지를 가장 우선적으로 내보낸다. → 미래 예측
   • FIFO에 비해 페이지 결함의 횟수를 많이 감소시킬 수 있다.
   • 하지만 실질적으로 페이지가 앞으로 잘 사용되지 않을 것이라는 보장이 없으므로 수행하기 어려운 알고리즘이다.
3. LRU(Least Recently Used) 알고리즘
   • 최근에 사용하지 않은 페이지를 가장 먼저 내려보내는 알고리즘 → 과거 판단
   • 최근에 사용하지 않았으면 나중에도 사용되지 않을 것이라는 생각에서 착안
   • 페이지 결함은 OPT보다 더 일어날 수 있지만 실제로 사용할 수 있는 페이지 교체 알고리즘에서는 가장 좋은 방법 중 하나이다.

교체 방식

1. Global 교체
   • 메모리 상의 모든 프로세스 페이지에 대해 교체하는 방식
2. Local 교체
   • 메모리 상의 자기 프로세스 페이지에서만 교체하는 방식

• 다중 프로그래밍의 경우, 메인 메모리에 다양한 프로세스가 동시에 올라올 수 있다. 그래서 다양한 프로세스의 페이지가 메모리에 존재하고 페이지 교체 시, 다양한 페이지 교체 알고리즘을 활용하여 victim page를 선정한다.
• 선정 기준이 Global, Local로 하느냐의 차이지만 실제로 전체 기준으로 페이지를 교체하는 것이 더 효율적이라고 한다. 자기 프로세스 페이지에서만 교체를 하면 교체를 해야할 때 각각 모두 교체를 진행해야 하므로 비효율적이다.