[운영체제] 가상 메모리

메모리(memory)

• 메모리란 프로그램과 프로그램 수행에 필요한 데이터 및 코드를 저장하는 장치
• 메모리는 크게 내부 기억장치인 주기억장치와 외부 기억장치인 보조 기억장치로 분류됨
  • DRAM, CPU 안에 있는 레지스터(register)와 캐시(cache memory)등이 전자에 해당됨
  • SSD, HDD 등이 후자에 해당됨

가상 메모리 등장 배경

• 초창기 컴퓨터에서는 사용 가능한 RAM의 용량이, 가장 큰 실행 애플리케이션의 주소 공간보다 커야 했다. 그렇지 않을 경우 "메모리 부족" 오류에 의해 해당 애플리케이션을 실행할 수 없었다.
• 이후 컴퓨터에서는 프로그래머가 애플리케이션의 일부분만 기억장치에 올려 실행하도록 지정할 수 있게 하는 어버레이 기법을 사용하여 메모리 부족 문제를 해결하고자 했다. 하지만 이 역시 전반적인 메모리 부족 문제를 해결할 수 없었다. 오버레이를 사용하는 프로그램은 그렇지 않은 프로그램보다는 메모리를 덜 사용했지만, 애초에 시스템이 프로그램을 위한 충분한 메모리를 갖추고 있지 않은 경우에는 결국 똑같은 메모리 부족 오류가 발생했다.
• 여기에서 더 발전한 가상 메모리 기법은 애플리케이션을 실행하는 데 얼마나 많은 메모리가 필요한지에 집중하지 않고, 대신 애플리케이션을 실행하는 데 최소한 얼마만큼의 메모리가 필요한가에 집중하여 문제를 해결하고자 했다.
  • 이렇게 접근하는 방식이 가능한 이유는, 메모리 접근은 순차적이고 지역화되어 있기 때문이다.
  • 그렇다면 이렇게 애플리케이션의 일부분만 메모리(기억장치)에 올려진다면, 메모리에 올라가지 않는 나머지는 어디에 위치해야 하는가? => 보조 기억장치, 즉 디스크! 이다.
  • 가상 메모리의 핵심은 보조 기억장치이다.

가상 메모리(Virtual Memory System)

실제 각 프로세스마다 충분한 메모리를 할당하기에는 메모리 크기가 한계가 있다.
가상 메모리는 메모리가 실제 메모리보다 많아 보이게 하는 기술로, 어떤 프로세스가 실행될 때 메모리에 해당 프로세스 전체가 올라가지 않더라도 실행이 가능하다는 점에 착안하여 고안되었다.

• 애플리케이션이 실행될 때, 실행에 필요한 일부분만 메모리에 올라가며 애플리케이션의 나머지 디스크에 남게 됨. 즉, 디스크가 RAM의 보조 기억장치(backing store)처럼 작동하는 것이다.
  • 결국 빠르고 작은 기억장치(RAM)를 크고 느린 기억장치(디스크)와 병합하여, 하나의 크고 빠른 기억장치(가상 메모리)처럼 동작하게 하는 것
• 가상 메모리 기본 아이디어
  • 프로세스는 가상 주소를 사용하고, 실제 해당 주소에서 데이터를 읽고/쓸 때만 물리 주소로 바꿔주면 된다.
  • virtual address (가상 주소): 프로세스가 참조하는 주소
  • physical address (물리 주소): 실제 메모리 주소
• 가상 메모리를 구현하기 위해서는 컴퓨터가 특수 메모리 관리 하드웨어를 갖추고 있어야만 한다. 그것이 바로 MMU(Memory Management Unit)
  • CPU에 코드 실행 시, 가상 주소 메모리 접근이 필요할 때, 해당 주소를 물리 주소 값으로 변환해주는 하드웨어 장치

페이징 시스템 (paging system)

• 페이징(paging) 개념
  • 크기가 동일한 페이지로 가상 주소 공간과 이에 매칭 하는 물리 주소 공간을 관리
  • 하드웨어 지원이 필요
  • 리눅스에서는 4KB로 paging
  • 페이지 번호를 기반으로 가상 주소/물리 주소 매핑 정보를 기록/사용

실질적인 예를 기반으로 페이징 시스템에 대해 알아보자.

• 프로세스(4GB)의 PCB(Process Control Block)에 Page Table 구조체를 가리키는 주소가 들어있다.
• Page Table에는 페이지 각각의 번호 별로 가상 주소와 그에 해당하는 물리 메모리 주소를 매핑해놓은 정보가 있다.

 

페이지 테이블은 페이지가 엄청 많으니까 당연히 길다. 그 페이지 테이블 맨 위에 접근할 수 있는 주소를 저장해놓는다.
위 그림을 참고해서 CPU가 어떤 가상 주소에 접근하려고 할 때를 생각해보자.
일단, 이 가상 주소를 통해 어떤 페이지 번호인지 바로 알 수 있을 것이다. 그 페이지 번호를 통해 PCB에 있는 페이지 테이블 구조에 들어가서 맨 위에서부터 몇 번째인지 찾아가며 매칭 되는 물리 주소를 알아낸다. 그 물리 주소를 갖고 실제 코 드난 데이터 정보를 갖고 CPU에 처리를 하게 된다.

페이징 시스템 구조

이제 좀 더 실질적으로 어떻게 동작하는지 살펴보자.

• page(=page frame): 고정된 크기의 block(4KB)
  • 총 9KB의 데이터가 있다고 할 때 데이터가 쭉 쓰이다 보면, page 1이 4KB, page 3 이 1KB라고 하면, 남는 3KB까지도 함께 물리 메모리에 넣는다. 이 물리 메모리의 주소는 페이지 테이블에 넣는다.
• paging system
  • 가상 주소 v=(p, d)
    • p: 가상 메모리 페이지
    • d: p안에서 참고하는 위치
      
      
    • 

페이지 테이블(page tabel)

• page table
  • 물리 주소에 있는 페이지 번호와 해당 페이지의 첫 물리 주소 정보를 매핑한 표
  • 가상 주소 v = (p, d) 라면
    • p : 페이지 번호
    • d : 페이지 처음부터 얼마 떨어진 위치인지
  • paging system 동작
    • 해당 프로세스에서 특정 가상 주소 엑세스를 하려면
      • 해당 프로세스 PCB에 있는 page table의 base 주소에 해당 가상 주소가 포함된 page 번호가 있는지 확인
      • page 번호가 있으면 이 page가 매핑된 첫 물리 주소(p')를 알아내면, p' + d가 실제 물리 주소가 됨
        
        

페이징 시스템과 MMU (컴퓨터 구조)

이제 MMU까지 합해서 살펴보자.
CPU는 가상 주소에 접근할 때 MMU 하드웨어 장치를 통해 물리 메모리에 접근한다.

 

 

이때, 가상 주소를 물리 주소로 변환시켜주는데, PCB는 페이지 테이블의 base 주소를 갖고 있으므로 PCB를 통해 해당 페이지 테이블에 접근이 가능하다. 이러한 페이지 테이블 관련 정보는 디폴트로 물리 메모리에 들어가 있다.
프로세스가 맨 처음에 실행될 때 , 페이지 테이블에 적재가 되면서 동시에 해당 페이지 테이블 base 주소가 별도 레지스터(CR3)에 저장되는 것이다.
그 후에 CPU가 해당 프로세스의 가상주소를 실행하기 위해 접근하게 되면, MMU가 CR3 레지스터를 가져와서 페이지 테이블 bse 주소를 참고해서 물리주소로 변환을 한 다음, 해당 물리 주소에 있는 데이터를 CPU에 가져다주게 된다.

 

TLB(Translation Lookaside Buffer, 페이지 정보 캐쉬)란?

TLB는 가상 메모리 주소를 물리적주소로 변환하는 속도를 높이기 위해 사용하는 캐시로, 최근에 일어난 가상 메모리와 물리 주소의 변환 테이블을 저장해둠. CPU가 가상 주소를 가지고 메모리에 접근하려고 할 때 우선은 TLB에 접근하여 가상 주소에 해당되는 물리 주소를 찾고, 만약 TLB에 매핑이 존재하지 않는다면 MMU가 페이지 테이블에서 해당되는 물리 주소로 변환한 후 메모리에 접근하게 된다.

• TLB는 일종의 주소 변환 캐시라고 할 수 있다.

캐시 메모리(chche memory)
캐시 메모리란, 속도가 빠른 장치와 느린 장치 사이에서 속도 차에 따른 병목 현상을 줄이기 위한 범용 메모리를 의미한다.
예를 들어, CPU에서의 캐시 메모리는 CPU 코어(고속)와 메모리(CPU에 비해 저속) 사이에서 속도 차에 따른 병목 현상을 완화하는 역할을 한다.
또한 인터넷 웹 브라우저에는 캐시 파일이라는 개념이 있는데 캐시 파일은 웹 페이지 상의 이미드 등을 하드디스크에 미리 저장해 두고, 다음번에도 해당 웹 페이지에 접근할 때 해당 사이트에 이미지를 다시 요청하는 게 아니라 하드디스크에서 이미지를 불러들여 로딩 속도를 높이는 역할을 한다. 즉, 캐시 파일은 비교적 속도가 빠른 하드디스크와 상대적으로 느린 웹 페이지 가운데서의 병목을 줄이는 역할을 한다.

• TLB 사용 이점: 물리 주소를 갖고 있으면 메모리(RAM)에 두 번 들릴 필요 없이, 바로 해당 물리 주소(in메로리)를 찾아갈 수 있다.

MMU와 TLB(컴퓨터 주소)

• MMU가 물리 주소를 확인하기 위해 메모리를 갔다 와야 함.

-> 문제는 메모리에 왔다 갔다 하는 시간이 많이 걸린다는 것이다.
이러한 문제를 해결하기 위해 별도의 캐쉬 보조 하드웨어를 갖다 놓는다.

 

A라는 가상 주소를 요청했더니 A라는 물리 주소가 나왔다고 해보자. 이 정보를 TLB에 저장하는 것이다. 그래서 그 다음부터는 A라는 가상주소를 다시 메모리 요청하면 페이지 테이블을 갔다오는 것이 아니라 MMU 단계에서 TLB를 찾아본다. 찾아봐서 여기에 A의 물리주소가 있으면 2,3, 번 작업을 안 하고 4번 작업으로 바로 가기 때문에 접근을 두 번에서 한 번으로 줄일 수 있다.

요구 페이징(demand paging)

요구 페이징은 CPU가 요청할 때 프로세스의 데이터를 메모리에 올리는 것을 의미한다. 즉, 처음부터 모든 데이터를 메로리로 적재하지는 않는다.

페이징 폴트(page faults)란?

페이지 폴트란 어떤 페이지에 접근하려고 했을 때 해당 페이지가 실제 물리 메모리에 부재할 때 뜨는 인터럽트이며, 페이지 폴트가 발생하면 운영체제가 이를 해결한 뒤 다시 동일한 명령을 수행하는 식으로 동작한다.

• 페이지 폴트란, 어떤 프로그램이 자신의 주소 공간(가상 메모리 공간)에는 존재하지만 시스템의 RAM에는 현재 존재하지 않는 데이터 코드에 접근을 시도할 경우 발생하는 현상을 의미한다.
• 페이지 폴트가 발생하면 운영체제는 그 데이터를 메모리로 가져와서, 마치 페이지 폴트가 전혀 발생하지 않은 것처럼 프로그램이 계속적으로 작동하게 해 준다.
• 이러한 페이지 폴트가 자주 일어날수록 운영체제의 성능이 많이 저하되기 때문에 페이지 폴트가 일어나지 않도록 하는 것이 중요하다. 페이지 폴트를 최소화하기 위한 방법으로는 페이지 교체 정책이 있다.
  • 메모리가 꽉 차 있을 때 기존 페이지 중 하나를 물리 메모리에서 저장 매체로 내리고, 새로운 페이지를 방금 비워진 해당 물리 메모리 공간에 올린다. 이때 기존 페이지 중 어떤 것을 내리면 좋을지에 대한 알고리즘을 짠 것이 바로 페이지 교체 알고리즘인 것이다.

페이지 폴트와 인터럽트

1. 맨 처음에 CPU가 가상 주소를 요청한다. 그리면 MMU는 우선 TLB에 가서 해당 가상 메모리에 대한 물리 주소가 있는지 확인한다.
   1. 물리주소가 TLB에 있으면 그 데이터(물리 주소)를 바로 메모리에 갖고 온 후, 바로 CPU에서 처리를 하면 된다.
   2. 만약 물리 주소를 모른다면, CR3 레지스터를 갖고 page table에 접근한다. 그리고 이때, valid-invalid bit를 보고 해당 물리 주소가 메모리에 저장되어있는지, 안 되어있는지 확인한다.
      1. 만약 물리 주소에 저장이 되어있다고 하면, MMU가 해당 물리 주소(해당 페이지의 데이터)를 갖고 와서 다시 CPU에 보내면 끝난다.
      2. 그런데 만약 invalid 상태라면 이 때는 page falut interrupt가 운영체제에 던져지게 된다. 운영체제는 page falut interrupt를 처리하기 위해서 해당 페이지를 저장 공간(ex. 실행파일)에서 갖고 와서 그 해당 데이터를 메모리에 올려준다. 그다음 page table을 업데이트하고, CPU에게 재실행을 요청한다. 그러면 CPU는 위 그림의 7번처럼 가상 주소를 다시 요청하고 MMU를 타서 해당 메모리에 있는 데이터를 CPU가 가져갈 수 있게 된다.

그 외로, page falut interrupt가 나면 원래는 IDT(Interrupt Discrete Table)에 가서 인터럽트 번호에 대한 OS 안에 있는 함수를 호출하고 4번과 같은 작업을 한다.

그런데 TLB를 바로 사용하는 것보다 당연히 페이지 폴트는 오래 걸리게 된다. 따라서 아래의 문제점들을 한 번 생각해볼 필요가 있다.

• 페이지 폴트가 자주 일어나면?
  • 실행되기 전에 해당 페이지를 물리 메모리에 올려야 한다.
    • 시간이 오래 걸린다.
• 페이지 폴트가 안 일어나게 하려면?
  • 향후 실행/참조될 코드/데이터를 미리 물리 메모리에 적정하게 올리면 된다.
    • 앞으로 있을 일을 예측해야 한다. - 신의 영역

 

페이지 교체 정책(page replacement policy)

• 운영체제가 특정 페이지를 물리 메모리에 올리려 하는데, 물리 메모리가 다 차있다면?
  • 기존 페이지 중 하나를 물리 메모리에서 저장매체로 내리고(저장)
  • 새로운 페이지를 해당 물리 메모리 공간에 올린다.

-> 어떤 페이지를 물리 메모리에서, 저장 매체로 내릴 것인가?
-> Page Replacement(Swapping) Algorithm

페이지 교체 알고리즘

FIFO(First In First Out) Page Replacement Algorithm

• 가장 먼저 들어온 페이지를 내리자

OPT(OPTimal Replacement) Algorithm

• 최적 페이지 교체 알고리즘
• 앞으로 가장 오랫동안 사용하지 않을 페이지를 내리자 -> 사실상 불가능. 일반 OS에서는 구현 불가

LRU(Least Recently Used) Page Replacement Algorithm

• 가장 오래전에 사용된 페이지를 교체
• OPT 교체 알고리즘이 구현 불가하므로, 과거 기록을 기반으로 시도

LFU(Least Frequently Used) Page Replacement Algorithm

• 가장 적게 사용된 페이지를 내림

NUR(Not Used Recently) Page Replacement Algorithm

• LRU와 마찬가지로 최근에 사용하지 않은 페이지부터 교체하는 기법
• 각 페이지마다 참조 비트(R), 수정 비트(M)를 둠(R, M)
  • (0,0), (0,1), (1,0), (1,1) 순으로 페이지 교체(0:false, 1:true)

 

스레싱(Thrashing)

반복적으로 페이지 폴트가 발생해서, 과도하게 페이지 교체 작업이 일어나, 실제로는 아무 일도 하지 못하는 상황