가상 메모리

가상 메모리란

---

• 가상 메모리라는 것은 프로세스 전체가 메모리 내에 올라오지 않아도 실행 가능하다는 것을 의미합니다. 
• 애플리케이션이 실행될 때, 실행에 필요한 일부분만 메모리에 적재되고, 나머지 부분은 디스크에 남게됩니다. 이렇게 메모리와 디스크를 병합하여, 하나의 가상 메모리처럼 동작하게 하는것입니다.
• 가상 메모리를 구현하기 위해서는 컴퓨터가 특수한 하드웨어 장치를 가지고 있어야 하는데 이를 MMU(Memory Managment Unit)이라 합니다.
• MMU는 논리 주소에 임의의 값을 더한 후 물리 주소에 접근할 수 있도록 해주는 장치입니다.

 

🤔 가상 메모리와 동적 적재의 차이점이 뭘까?

 

• 가상 메모리는 프로세스 전체가 메모리에 올라와 있지 않아도 실행이 가능합니다. 반면 동적 적재도 이와 비슷합니다. 비슷하면서도 다른점이 무엇일까요?
• 가상 메모리는 물리적 메모리를 관리하는 기술이고, 동적 적재는 프로그램의 필요한 부분만 메모리에 적재하여 실행의 효율성을 높이는 기술입니다. 동적 적재는 프로그램 실행의 효율성을 높이기 위해 사용하는 기술입니다. 프로그램을 한 번에 메모리에 적재하는 대신 런타임 시점에 필요한 부분만 적재하여 프로그램이 사용하는 메모리 양을 줄이고, 시스템 전반적인 성능을 향상시킬 수 있습니다.

 

요구 페이징

---

• 요구 페이징은 가상 메모리 시스템에서 일반적으로 사용되며, 처음부터 모든 데이터가 메모리에 적재되어 있지 않고, 필요한 일부 데이터만 메모리에 적재하고, 나머지는 보조저장장치에 있습니다.
• 데이터가 메모리에 있는지, 보조저장장치에 있는지 구분하기 위해서는 하드웨어의 지원이 필요합니다. 무효/유효 비트 기법을 사용하여 구분할 수 있습니다.
• 비트가 유효하다고 설정되면 해당 페이지가 메모리에 있다는 의미이고, 무효하다고 설정되면 해당 페이지가 가상 주소 공간에 존재하지 않거나 유효하지만 보조저장장치에 존재한다는 것을 의미합니다.

 

💡 페이지 폴트

 

• 페이지 폴트란 프로세스가 메모리에 올라와 있지 않은 페이지에 접근하려고 할 때 발생하게 됩니다. 페이지 폴트가 발생하면 운영체제가 이를 해결한 뒤 다시 동일한 명령을 수행하는 방식으로 동작합니다.

페이지 폴트가 처리되는 과정

    페이지 폴트 과정

 

1. 프로세스가 페이지 테이블을 검사해 해당 메모리 참조가 유효 비트인지 무효 비트인지 확인합니다.
2. 무효비트라면 트랩을 발생시킵니다. 유효 비트더라도 메모리에 없으면 트랩을 발생시킵니다.
3. 유효비트인데 페이지가 보조저장장치에 있으면 보조저장장치에 접근합니다.
4. 보조저장장치로부터 가져옵니다. 또한 물리 메모리에 가용한 프레임을 찾으며, 해당 프레임에 페이지를 채웁니다.
5. 해당 페이지가 메모리에 있다는 것을 알리기 위해 페이지 테이블을 갱신합니다.
6. 트랩에 의해 중단된 명령어를 다시 수행합니다. 이제 프로세스는 마치 그 페이지가 항상 메모리에 있었던 것처럼 해당 페이지에 접근할 수 있습니다.

 

💡 순수 요구 페이징

 

• 극단적인 경우 메모리에 페이지가 하나도 안 올라와 있는 상태에서도 프로세스를 실행시킬 수 있습니다.
• 운영체제에서 명령어 포인터의 값을 프로세스의 첫 명령으로 실행하는 순간, 해당 명령이 메모리에 존재하지 않으므로 페이지 폴트를 발생시킵니다. 또한 페이지가 적재되고 나면 프로세스는 수행을 계속하는데 필요한 페이지가 메모리에 적재될 때까지 페이지 폴트를 발생시킵니다. 이렇게 필요한 모든 페이지가 적재되고 나면 더 이상 페이지 폴트가 발생하지 않는데, 이를 순수 요구 페이징이라 합니다. 즉 어떤 페이지가 필요해지기 전까지 결코 그 페이지를 메모리에 적재하지 않는 방법입니다.

 

💡 가용 프레임 리스트

 

• 페이지 폴트가 발생하면 운영체제는 요청된 페이지를 보조저장장치에서 메인 메모리로 가져와야 합니다. 페이지 폴트를 해결하기 위해 대부분의 운영체제는 가용 프레임 풀인 가용 프레임 리스트를 유지합니다.
• 운영체제는 일반적으로 zero-fill-on-demand라는 기법을 사용하여 가용 프레임을 할당합니다. zero-fill-on-demand 프레임은 할당되기 전에 "0 으로 모두 채워져" 이전 내용이 지워집니다.
• 시스템이 시작되면 모든 가용 메모리가 가용 프레임 리스트에 채워집니다. 가용 프레임이 요청되면 가용 프레임 리스트에서 하나를 할당하게 되며, 크기가 줄어듭니다.

 

쓰기 시 복사(Copy on Write)

---

• 요구 페이징 및 순수 요구 페이징을 통해 프로세스를 빠르게 실행시킬 수 있다는 것을 알게되었습니다. 그러나 fork() 시스템 콜을 통해 프로세스를 생성할 때는 첫 요구 페이징조차 생략할 수 있습니다.
• 쓰기 시 복사를 통해 프로세스 생성 시간이 더 줄어들 수 있고, 새로 생성된 프로세스에 새롭게 할당되어야 하는 페이지의 수도 줄일 수 있습니다.
• fork 시스템 콜을 하면 부모 프로세스의 페이지들을 자식 프로세스에게 복사해줌으로써 자식 프로세스의 주소 공간을 구성해주었는데 이 방법은 비효율적입니다. 그 이유는 대부분의 자식 프로세스는 만들어지자마자 곧 exec 시스템 콜을 합니다. 

 

    Copy-on-Write

 

• copy-on-write 방식은 자식 프로세스를 생성할 때 부모의 페이지를 당분간 함께 사용하는 방식입니다. 이때 공유되는 페이지를 copy-on-write라고 표시합니다. 둘 중 한 프로세스가 공유 중인 페이지에 쓸 때 그 페이지의 복사본이 만들어진다는 의미입니다.
• 운영체제는 가용 프레임 리스트에서 프레임을 얻고, 이 페이지의 복사본을 만들어 자식 프로세스의 주소 공간에 사상시킵니다. 따라서 자식은 그 개인용으로 만든 페이지에 수정을 하게됩니다. 이렇게 하면 프로세스가 수정하는 페이지에 대해서만 복사본이 생기고, 수정되지 않은 페이지들은 자식과 부모 간에 계속 공유될 수 있습니다.

    Copy-on-Write와 vfork 시스템 콜

 

• vfork 시스템 콜을 하면 부모 프로세스는 보류되고 자식이 부모의 주소 공간을 사용하게 됩니다. 하지만 vfork 시스템 콜은 copy-on-write를 사용하지 않으므로, 자식이 부모 주소 공간에 페이지를 수정하게 되면 변경된 페이지가 부모 프로세스가 재실행될 때 보여지게 됩니다. 그렇기 때문에 vfork 시스템 콜을 사용할 때는 자식이 부모의 페이지에 변경을 가하지 않도록 주의해야 합니다.

 

페이지 교체

---

• 프로세스가 실행되는 동안 페이지 폴트가 발생하게 됩니다. 운영체제는 필요로 하는 페이지가 보조저장장치에 저장된 위치를 알아내어 물리 메모리의 가용 프레임에 올릴려고 하지만 가용 프레임이 없음을 발견합니다. 이때 운영체제는 몇가지 선택을 할 수 있습니다. 예를들어 다른 프로세스를 종료한다던가, 스와핑 기법을 사용한다던가 할 수 있지만 이는 오버헤드를 유발하게 됩니다. 그렇기 때문에 대부분의 운영체제는 페이지 교체 기법을 사용하게 됩니다.

 

💡 페이지 교체 과정

 

1. 보조저장장치에서 필요한 페이지의 위치를 알아냅니다.
2. 물리 메모리에서 가용한 프레임을 찾습니다.
   1. 가용한 프레임이 존재한다면 해당 프레임을 사용합니다.
   2. 가용 프레임이 없다면 희생될 프레임을 선정하기 위해 프레임 교체 알고리즘을 가동시킵니다.
   3. 희생될 프레임을 보조저장장치에 기록하고, 사용하고자 하는 데이터를 물리 메모리에 적재합니다.
3. 물리 메모리에 적재되었으니 페이지 테이블을 갱신합니다.
4. 페이지 폴트가 발생한 지점부터 다시 프로세스를 재개합니다.

 

페이지 교체 알고리즘

---

💡 FIFO 알고리즘

 

• FIFO 페이지 교체 알고리즘은 어떤 페이지를 교체해야하는 경우 메모리에 올라온 지 가장 오래된 페이지를 희생시킵니다.
• 페이지가 올라온 시간을 페이지마다 기롣해도 되고, 아니면 페이지가 올라온 순서대로 큐에 적재시켜도 됩니다.

    Belady의 모순

 

• Belady의 모순이란 프로레스에게 프레임을 더 할당해주었지만 오히려 페이지 폴트율이 증가하는 현상을 말합니다.
• 페이지 교체 알고리즘에서 Belady의 모순 현상을 나타내지 않는 것들이 있는데 그것은 스택 알고리즘으로 구현된 것들입니다.

💡 LRU 알고리즘

 

• LRU 페이지 교체는 가장 오랜 기간 동안 사용되지 않은 페이지를 교체하는 기법입니다.
• LRU 페이지 교체 알고리즘은 페이지마다 마지막 사용 시간을 유지합니다. 따라서 페이지가 교체될 때 마지막 사용 시간을 참고해 가장 오랫동안 머물러 있던 페이지를 교체하게 됩니다.
• LRU 페이지 교체 알고리즘은 하드웨어의 지원이 필요합니다. 그 이유는 프레임들이 최근 사용된 시간 순서를 파악할 수 있어야 되기 때문입니다.

 

💡 LRU 근사 페이지 교체

 

• LRU 페이지 교체 지원을 충분히 할 수 있는 하드웨어는 많지 않습니다. 어떤 시스템에서는 FIFO와 같은 알고리즘을 사용할 수 밖에 없는데 이때 참조 비트를 사용하여 알고리즘을 구현하는 것입니다.
• 페이지 참조가 있을 때마다(페이지를 읽거나 쓸때) 히드웨어가 그 페이지에 대한 참조 비트를 설정합니다. 참조 비트는 페이지 테이블에 있는 각 항목과 대응됩니다. 처음에 모든 참조비트는 운영체제에 의해 0으로 설정되며, 프로세스가 실행되면서 참조되는 페이지의 비트는 하드웨어가 1로 세팅합니다.

 

💡 LFU 알고리즘 (least frequently used)

 

• LFU 알고리즘은 참조 횟수가 가장 적은 페이지를 교체하는 방법입니다. 가장 작은 참조 횟수를 선택하는 이유는 활발하게 사용되는 페이지는 큰 참조 횟수를 갖게 될 것이라는 점입니다.
• 프로세스가 초기 단계에서는 한 페이지를 집중적으로 많이 사용하지만(참조 지역성) 그 후 이 페이지를 사용하지 않는 경우 판단이 빗겨나 갈 수 있습니다. 그렇게 되면 처음에는 사용했지만 시간이 지남에 따라 사용하지 않더라도 계속 메모리에 머물게 되는데 이 해결 방법은 참조 횟수를 일정 시간마다 줄이는 것입니다.

 

💡 MFU 알고리즘 (most frequently used)

 

• MFU 알고리즘은 LFU 알고리즘과 반대로 참조 횟수가 가장 많은 페이지를 교체하는 방법입니다.

 

💡 페이지 버퍼링 알고리즘

 

• 시스템들이 가용 프레임 여러개를 풀(pool)로 가지고 있다가, 페이지 폴트가 발생하면 교체될 페이지의 내용을 디스크에 기록하기 전에 가용 프레임에 새로운 페이지를 먼저 읽어 들이는 방법입니다. 
• 이 방법은 교체될 페이지가 디스크에 쓰이기를 기다리지 않고 프로세스가 가능한 한 빨리 시작할 수 있도록 해주는 방법입니다. 이후에 교체될 때 페이지가 다 쓰이고 나면 그 프레임이 가용 프레임 풀에 추가됩니다.

 

프레임 할당

---

• 여러 개의 프로세스에게 제한된 프레임을 어떻게 할당해야 하는지 알아보겠습니다.

 

💡 프로세스가 가져야하는 최소한의 프레임 수 

 

• 프로세스가 최소한의 프레임 수를 가져야하는 이유는 성능과 관계가 있습니다. 만약 프로세스에게 할당되는 프레임의 수가 적으면 페이지 폴트율이 증가하게 되고, 프로세스의 실행은 늦어지게 됩니다. 또한 명령어 수행 중 페이지 폴트가 발생하면 해당 명령어를 재실행해야 합니다. 따라서 명령어가 참조하는 모든 페이지는 메모리에 올라와 있어야 명령어를 무사히 끝낼 수 있습니다.
• 최소 프레임 수는 컴퓨터 아키텍처에 의해 정의됩니다.
• 프로세스당 최소 프레임 수는 컴퓨터 아키텍처에 의해 정의되고, 최대 수는 사용 가능한 물리 메모리에 의해 정의됩니다.

 

💡 할당 알고리즘

 

• 할당 알고리즘에는 균등 할당과 비례 할당이 있습니다.
• 균등 할당이나 비례 할당은 모두 높은 우선순위의 프로세스와 낮은 우선순위의 프로세스를 동등하게 취급합니다. 

 

    균등 할당

 

• n개의 프로세스에게 m개의 프레임을 할당하는 방법은 m/n 만큼 할당하는 방법입니다. 이처럼 균일하게 할당하는 방법입니다.

    비례 할당

 

• 각 프로세스의 크기를 고려하여 가용 메모리를 프로세스의 크기 비율에 맞추어 할당하는 방법입니다.

 

💡 전역할당과 지역할당

 

• 프레임을 할당하는 방법에서 다른 중요한 요소는 다수의 프로세스가 프레임 할당을 위해 경쟁하는 환경에서 페이지 교체 알고리즘은 크게 두가지로 나눌 수 있습니다.

 

    전역 교체

 

• 전역 교체는 프로세스가 교체할 프레임을 다른 프로세스에 속한 프레임을 포함하여 모든 프레임을 대상으로 찾는 것입니다.
• 우선순위가 높은 프로세스는 자신보다 우선순위가 낮은 프로세스에 접근하여 해당 프로세스의 프레임 중에서 희생자를 선택할 수 있습니다. 따라서 하나의 프로세스가 가지는 프레임 수는 유동적으로 변경됩니다.
• 다른 프로세스의 페이징 동작에도 영향을 미치고, 영향을 받습니다.

    지역 교체

 

• 지역 교체는 각 프로세스가 자신에게 할당된 프레임 중에서만 교체될 희생자를 찾는 것입니다.
• 지역 교체는 자신에게 할당된 프레임 수는 변하지 않습니다.
• 지역 교체는 잘 사용하지 않는 페이지 프레임이 있더라도 그것을 그대로 낭비를 해버립니다. 그렇기 때문에 일반적으로 지역 교체보다 전역 교체가 더 좋은 시스템 성능을 나타내며, 많이 사용됩니다.

 

스래싱

---

• 프로세스에 충분한 프레임이 없는 경우, 페이지 폴트가 발생하게 됩니다. 하지만 해당 프로세스는 곧바로 페이지 폴트를 발생시킵니다. 이렇게 활발하게 사용되는 페이지들만 이루어져 있으므로 계속하여 페이지 폴트가 발생하게 되는데, 이러한 과도한 페이징 작업을 스래싱이라 합니다.
• 스래싱이란 페이지 폴트율이 높은 것입니다.

 

💡 스래싱의 원인

 

• 운영체제는 CPU 이용률을 감시합니다. 만약 CPU 이용률이 너무 낮아지면 새로운 프로세스를 시스템에 추가하여 다중 프로그래밍의 정도를 높입니다. 이때 새로운 프로세스가 실행되면서 페이지 폴트가 발생하게 되는데, 페이지 폴트가 발생하면 다른 프로세스의 프레임을 가져오게 됩니다. 하지만 가져온 프레임들은 해당 프로세스에서 사용하고 있었다면 다시 페이지 폴트가 발생하게 됩니다. 이러한 작업이 진행되면 스왑인, 스왑아웃 하는 시간동안 CPU 이용률은 낮아지게 되고, CPU 스케줄러는 다시 새로운 프로세스를 추가하려고 합니다. 하지만 결국 악순환이 반복되어 CPU 처리율은 대단히 낮아지고 페이지 폴트는 많아지게 됩니다. 

 

    해결 방법 1)

 

• 지역 교체 알고리즘(또는 우선순위 교체 알고리즘)을 사용하여 스래싱의 영향을 제한할 수 있습니다. 하지만 이는 페이징 장치의 평균 대기열 시간이 길어지기 때문에 페이지 폴트의 평균 서비스 시간이 늘어나게 됩니다. 따라서 스래싱되지 않은 프로세스에서도 실질 접근 시간이 증가하게 됩니다.

    해결 방법 2)

 

• 각 프로세스가 필요로 하는 최소한의 프레임 수를 보장해야 하는 것입니다.
• 어떻게 각 프로세스들이 필요로 하는 프레임 수를 알 수 있을까? 에 대한 답은 지역성 모델 기법을 사용하는 것입니다. 지역성 모델이란 프로세스가 실행될 때에는 항상 어떤 특정한 지역에서만 메모리를 집중적으로 참조함을 말합니다.

 

커널 메모리 할당

---

• 사용자 모드에서 수행 중인 프로세스가 추가적인 메모리를 요구하면 커널이 관리하는 가용 페이지 프레임에서 페이지들이 할당됩니다. 
• 사용자가 단 한 바이트만을 필요로 하는 경우라면 프로세스가 한 페이지 프레임을 할당받았으므로 내부 단편화가 발생하게 됩니다.
• 커널 메모리는 보통 사용자 모드 프로세스에게 할당해 주기 위한 페이지 리스트와는 별도의 메모리 풀에서 할당받습니다.
• 메모리 풀에서 할당받는 이유는 다양한 크기의 자료구조를 할당할 수 있이며, 내부 단편화에 의한 낭비를 최소화합니다. 또한 사용자 모드 프로세스에 할당되는 페이지들은 물리 메모리에서 굳이 연속적일 필요가 없기 때문입니다.

 

💡 할당되는 메모리를 관리하는 기법

 

    버디 시스템

 

• 버디 시스템은 물리적으로 연속된 페이지들로 이루어진 고정된 크기의 세그먼트로부터 메모리를 할당합니다. 
• 메모리는 2의 거듭제곱 할당기에 의해 2의 거듭제곱 단위로 할당됩니다.(2KB, 4KB, 8KB, 16KB, 32Kb ...) 2의 거듭제곱 크기가 아닌 메모리를 요구하면 가장 가까운 2의 거듭제곱 크기로 줍니다.
• 이 방법은 내부 단편화를 발생시킵니다.
• 큰 메모리는 두 개의 버디로 나누어집니다. 또한 합병이라는 과정을 통해 인접한 버디들이 손쉽게 하나의 세그먼트로 합쳐질 수 있습니다.

    슬랩 할당

 

• 슬랩은 하나 또는 그 이상의 연속된 페이지들로 구성됩니다. 캐시는 하나 또는 그 이상의 슬랩으로 구성됩니다. 각 커널 자료구조마다 하나의 캐시가 존재합니다.
• 예를들어 파일 객체를 위한 캐시, 세마포어를 위한 캐시 등이 존재하며, 각 캐시는 커널 자료구조의 각 인스턴스에 해당하는 객체들로 채워집니다. (세마포어 캐시는 세마포어 객체들로 저장)
• 슬랩 할당 알고리즘은 커널 객체를 저장하기 위해 캐시를 사용합니다. 캐시가 생성되면 초기에는 free라고 표시된 몇 개의 객체들이 캐시에 할당됩니다. 캐시 내의 객체 수는 해당 슬랩의 크기에 좌우됩니다.

 

    장점

 

• 내부 단편화에 의한 메모리 낭비가 발생하지 않습니다. 커널이 메모리를 할당을 요구할 때마다 슬랩 할당기는 정확히 필요한 만큼의 메모리만 할당합니다.
• 메모리 요청이 빠르게 처리됩니다. 객체들은 미리 생성되어 있고 캐시에서 쉽게 할당이 가능합니다. 또한 사용후에는 캐시 상태로 반환되어 다음 요규 시 즉시 할당 가능하게 됩니다.