[운영체제] 10. 가상 메모리

아래 도서 기반 정리

운영체제 | Abraham Silberschatz - 교보문고

목차

• 배경
• 요구 페이징
• 쓰기 시 복사
• 페이지 교체
• 프레임의 할당
• 스래싱
• 메모리 압축

 

배경

---

실제 프로그램을 보면 많은 경우에 프로그램 전체가 한꺼번에 메모리에 늘 올라가 있어야 하는 것은 아니다.
만약 프로그램을 일부분만 메모리에 올리고 실행 가능하다면, 아래와 같은 이점이 있다.

• 프로그램은 물리 메모리 크기에 제약받지 않을 수 있다.
• 각 프로그램이 더 작은 메모리를 사용하므로, 더 많은 프로그램을 동시에 수행할 수 있다.
  따라서 응답시간은 늘어나지 않고, CPU 이용률과 처리율이 높아진다.
• 프로그램을 메모리에 올리고 swap 하는데 필요한 I/O 회수가 줄어들기 때문에, 프로그램이 보다 빨리 실행된다.

 

가상 메모리 (Virtual Memory)

실제의 물리 메모리 개념과 개발자의 논리 메모리 개념을 분리한 것이다.

CPU가 프로세스를 실행할 때는 가상 메모리 주소를 사용하고,
실제 해당 가상 주소에서 데이터를 읽고 쓸 때만 물리 메모리 주소로 접근해서 실행한다.

• 작은 메모리를 가지고도 큰 가상 주소 공간을 프로그래머에게 제공할 수 있다.
• 프로그래머가 메모리 크기에 관련한 문제를 염려할 필요 없이 쉽게 프로그램을 작성할 수 있게 해준다.

 

가상 주소 공간 (Virtual Address Space)

프로세스가 메모리에 저장되는 논리적인 || 가상적인 모습(view)을 말한다.
이 시각에선 일반적으로 특정 논리 주소에서 시작해 연속적인 공간을 차지할 것이다.

힙과 스택 사이의 공백도 가상 주소 공간의 일부다.
힙 또는 스택이 확장되어야 실제 물리 페이지를 요청하게 된다.
공백을 포함하는 가상 주소 공간을 성긴(sparse) 주소 공간이라고 한다.

 

가상 메모리는 페이지 공유를 통해 파일이나 메모리가 둘 또는 그 이상의 프로세스 들에 의해 공유될 수 있게 한다.

• 프로세스는 메모리를 공유할 수 있다.
• 두 개 이상의 프로세스는 공유 메모리로 통신이 가능하다.
• 가상 메모리를 사용하면 한 프로세스에서 다른 프로세스가 공유할 수 있는 메모리를 생성할 수 있다.
• 이 영역을 공유하는 프로세스들은 자신의 가상 주소 공간이라고 간주하지만, 실제로는 메모리 내의 물리 페이지가 공유되고 있다.
• 페이지는 fork() 시스템 호출로 프로세스 생성 시 공유할 수 있어 프로세스 생성이 빨라진다.

 

요구 페이징 (Demand Paging)

---

프로그램의 전부를 메모리에 올리는 것이 아닌, 프로그램 실행 중 필요할 때만 페이지를 적재하는 기법이다.

• 필요한 프로그램의 일부만 적재해, 메모리가 더 효율적으로 사용된다.

 

valid-invalid bit 기법

프로세스가 실행되는 동안 일부 페이지는 메모리에 있고, 일부는 보조 저장 장치에 있다.
이 둘을 구별하기 위해 사용하는 기법으로 메인 메모리 단원에서 설명했다.

• 유효 (valid) : 해당 페이지가 메모리에 있다는 의미다.
• 무효 (invalid)
  1. 해당 페이지가 유효하지 않다. || 가상 주소 공간상에 정의되지 않았다. 라는 의미다.
  2. 유효하지만, 보조 저장 장치에 존재한다는 의미다.

 

페이지 폴트 트랩 (Page-fault trap)

프로세스가 메모리에 올라가있지 않은 페이지 접근해, 페이지 테이블 항목이 무효로 설정되어 있을 때 발생하는 트랩이다.

• 접근하려는 것이 invalid bit일 때 발생

 

페이지 폴트 처리 과정

1. 프로세스에 대한 내부 테이블을 검사해 메모리 참조가 유효인지 무효인지 알아낸다.
2. 만약, 무효한 페이지라면 그 프로세스는 중단된다.
   유효한 페이지인데 아직 메모리에 올라오지 않았다면, 보조 저장 장치로부터 가져와야 한다.
3. 가용 프레임(free frame)을 찾는다.
4. 보조 저장 장치에 새로이 할당된 프레임으로 해당 페이지를 읽어 들이도록 요청한다.
5. 보조 저장 장치 읽기가 끝나면, 이 페이지가 이제는 메모리에 있다는 것을 알리기 위해 페이지 테이블을 갱신해, 프로세스가 유지하는 내부 테이블을 수정한다.
6. 트랩에 의해 중단됐던 명령어를 다시 수행한다.'

 

순수 요구 페이징 (Pure demand paging)

극단적인 경우에는 메모리에 페이지가 하나도 안 올라와 있는 상태에서 프로세스를 실행시킬 수도 있다.
이 경우 프로세스가 사용하는 모든 페이지가 메모리에 올라올 때까지 필요할 때마다 페이지 폴트가 발생한다.
후에 필요한 모든 페이지가 적재되고 나면, 더 이상 폴트가 발생하지 않는다.
이처럼 어떤 페이지가 필요해지기 전에는 결코 그 페이지를 메모리로 적재하지 않는 방법이다.

 

참조 지역성 (Locality of reference)

한 명령어에서도 여러 개의 페이지 폴트가 발생할 수 있다.
이렇게 되면 시스템 성능의 저하가 초래될 것이다.
다행히 이러한 경우는 거의 발생하지 않는다.

프로그램은 참조 지역성이라는 성질이 있어 한 특정 부분만 집중적으로 참조한다.
이러한 성질 때문에 요구 페이징은 만족할 만한 성능을 보인다.

+++ 학교 자료
Backing store가 일반 파일 시스템보단 빠르지만, 디스크기 때문에 계속 접근하면 컴퓨터가 느려진다.
따라서 프로세스가 요청하는 일정 시간 || 구간 동안에는 일정 영역을 크게 벗어나지 않고, 기존에 참조했던 page ||  그 page와 가까운 page를 요청하려는 경향이다.

 

가용 프레임 리스트 (Free Frame List)

페이지 폴트를 해결할 때 쓰이는 가용 프레임 풀(pool)

• 프로세스의 스택 또는 힙 세그먼트가 확장될 때도 가용 프레임이 할당된다.

 

zero-fill-on-demand 기법

가용 프레임이 할당되기 전에 0으로 모두 초기화 해두는 기법이다.
프레임에 페이지를 적재하기 전 보안을 위해 초기화하는 것이다.

 

요구 페이징의 성능

요구 페이징은 컴퓨터 시스템 성능에 큰 영향을 줄 수 있다.

요구 페이지 메모리에 대한 실질 접근 시간은 페이지 폴트율(page fault rate)에 비례한다.
페이지 폴트율이 높을수록 컴퓨터가 느려지는 것이다.

따라서 페이지 폴트율을 낮게 유지해야한다.

또 다른 특성으론 스왑 공간의 관리다.

스왑 공간에서 디스크 I/O는 파일 시스템에서 보다 더 큰 블록을 사용하기 때문에 더 빠르다.

따라서 프로그램이 처음 시작할 땐 파일 시스템으로부터 요구 페이징을 처리하지만, 그 페이지들이 교체될 때는 스왑 공간에 페이지를 기록한다. 이는 페이지를 다시 읽어올 때 스왑 공간에서 읽어온다는 것을 보장한다.

 

쓰기 시 복사 (Copy on write)

---

fork() 시, 부모 프로세스의 페이지를 실제로 자식 프로세스에게 복사해줌으로써 자식 프로세스의 주소 공간을 구성했다.
그러나 대부분의 자식은 곧 exec() 시스템 콜을 호출한다.
그러면 부모로부터 복사해온 페이지들은 다 쓸모없는 것들이 된다.

부모의 페이지를 다 복사하는 대신 쓰기 시 복사 (copy-on-write) 방식을 사용할 수 있다.

• 자식 프로세스가 시작할 때 당분간 부모의 페이지를 함께 사용한다.
• 복사 페이지 : 공유되는 페이지
• 둘 중 한 프로세스가 공유중인 페이지를 쓸 때 그 페이지의 복사본이 만들어진다.

vfork() (virtual memory fork)

이 시스템콜은 자식이 부모의 주소공간을 사용하게 된다.
쓰기 시 복사를 사용하지 않으므로 자식이 부모 주소 공간의 페이지를 수정하면, 변경된 페이지가 재실행 시 부모 프로세스에 그대로 보인다.
따라서 vfork()는 자식이 부모 주소 공간의 페이지들에 변경을 가하지 않도록 주의해야 한다.

해당 시스템콜은 자식이 만들어지자마자 exec() 시스템콜을 호출하는 경우를 위해 마련된 것이다.
페이지가 전혀 복사되지 않으므로, 매우 효율적이다.

 

페이지 교체 (Page Replacement)

---

page fault가 발생했을 때, 가용 프레임(free frame)이 없는 경우 메모리 과할당(over-allocating)이 발생한다.
이 때, 빈 프레임이 없다면 현재 사용되지 않는 프레임을 찾아 그것을 비우는 방법이다.

• 프레임 할당 (frame-allocation) 알고리즘
  • 프로세스마다 몇 개의 프레임을 할당해야 효율적인가 결정하는 알고리즘
• 페이지 교체 (page-replacement) 알고리즘
  • 희생자를 선정하는 알고리즘
  • 가용 프레임이 없을 때, 현재 사용되지 않는 프레임을 찾아 비워버린다.
    그 프레임의 내용을 스왑 공간에 작성하고, 페이지 테이블을 변화시켜 프레임이 비어있음을 나타낸다.
  • 주로 페이지 폴트율이 가장 낮은 것을 선택
• 보조 저장 장치 I/O 비용은 매우 비싸다.
• 요구 페이징 방법은 조금만 개선해도 시스템의 전체 성능이 크게 향상될 수 있다.

 

FIFO 페이지 교체

어떤 페이지를 교체할 때, 메모리에 올라온지 가장 오래된 페이지를 교체하는 알고리즘

• 이해하기 쉽고, 프로그램 하기도 쉽다.
• 그러나 성능이 항상 좋진 않다.
• 교체된 페이지가 초기화된 뒤 계속해서 자주 사용되는 변수를 포함할 수 있다.
• 잘못된 교체 결정은 페이지 폴트율을 높이고, 프로세스 실행 속도를 떨어뜨린다.
• Belady 모순이 발생할 수 있다.

 

Belady 모순 (Belady's anomaly)

프로세스에 프레임을 더 주었는데 오히려 페이지 폴트율은 더 증가하는 현상

 

최적 페이지 교체 (Optimal Page Replacement)

앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아 교체하는 알고리즘

• 해당 알고리즘은, 할당된 프레임 수가 고정된 경우 가장 낮은 페이지 폴트율을 보장한다.
• 실제 구현은 어렵다.
  앞으로 프로세스가 메모리를 어떻게 참조할 것인지 미리 알아야 하기 때문이다.

 

LRU 페이지 교체 (Least-Re-Used Page Replacement)

가장 오랫동안 사용하지 않은 페이지를 선택해 교체하는 알고리즘

• FIFO 보다 훨씬 우수하다.
• 페이지 교체 알고리즘으로 자주 사용된다.
• 그러나 구현에는 하드웨어 지원이 필요하다. 최근 사용된 시간 순서로 파악할 수 있어야 하기 때문이다.
• Belady 모순 현상이 나타나지 않는다.

 

계수-기반 페이지 교체 (Counting-Based Page Replacement)

각 페이지를 참조할 때마다 계수를 해 다음과 같은 두 기법을 만든다.

하지만, 두 알고리즘 다 잘 쓰이지는 않는다.
구현 비용이 많이 들고, 최적 페이지 교체 정책을 제대로 근사하지 못 하기 때문이다.

LFU 알고리즘 (Least Frequently Used)

• 참조 횟수가 가장 작은 페이지를 교체하는 알고리즘
• 하지만, 일정 시간만 집중적으로 사용하고 그 이후론 사용되지 않는 페이지가 존재할 수 있다.
• 이를 해결하는 한 가지 방법은, 참조 횟수를 일정 시간마다 하나씩 오른쪽으로 시프트해 지수적으로 영향력을 감소시킨다.

MFU 알고리즘 (Most Frequently Used)

• 가장 작은 참조 횟수를 가진 페이지가 가장 최근 참조된 것이고, 앞으로 사용될 것이라는 판단에 근거한다.

 

프레임의 할당

---

여러개의 프로세스들에 제한된 가용 메모리를 어떻게 할당할 것인가?

최소로 할당해야 할 프레임 수 (Minimum Number of Frames)

각 프로세스에 할당되는 프레임 수가 줄어들면, 페이지 폴트율은 증가하고, 프로세스 실행은 늦어진다.
또 명령어 수행이 완료되기 전 페이지 폴트가 발생하면, 그 명령어는 재실행되어야 한다.
따라서 하나의 명령어가 참조하는 모든 페이지는 동시에 메모리에 올라와 있어야 한다.

 

균등 할당 (Equal Allocation) 알고리즘

모두에게 같은 몫의 프레임을 주는 알고리즘이다.
운영체제가 사용해야하는 프레임은 제외된다.

 

비례 할당 (Proportional Allocation) 알고리즘

가용 메모리를 각 프로세스의 크기 비율에 맞춰 할당하는 알고리즘이다.

 

전역 교체 (Global Replacement) 알고리즘

프로세스가 교체할 프레임을 다른 프로세스에 속한 프레임을 포함한 모든 프레임을 대상으로 찾는 알고리즘이다.

 

지역 교체(Local Replacement) 알고리즘

각 프로세스가 자기에게 할당된 프레임 중에서만 교체될 희생자를 선택하는 알고리즘이다.

 

스래싱 (Thrashing)

---

작업 집합의 페이지를 지원하는데 필요한 최소 프레임이 없는 경우 페이지 폴트로 페이지 교체가 발생한다.
이 때, 이미 활발하게 사용되는 페이지 들로만 이루어져, 바로바로 반복해서 페이지 폴트가 발생할 수 있다.

이처럼 과도한 페이징 작업을 스래싱이라고 한다.

스래싱이 발생하면 멀티 프로그래밍 정도를 낮추어야 CPU 이용률을 높이고 스래싱을 중지시킬 수 있다.

• CPU 이용률이 감소하면, 새로운 프로세스를 시스템에 추가해 멀티 프로그래밍 정도를 높인다. 전역 페이지 교체 알고리즘을 사용한다.
• 이 때 어떤 프로세스가 새로운 실행 단계로 진입해 더 많은 프레임이 필요할 수 있다.
• 페이지 폴트가 발생하면, 다른 프로세스로부터 프레임을 가져올 것이다.
• 그러나, 교체된 페이지들이 해당 프로세스에서 필요로 하는 것이었다면, 또 다시 페이지 폴트가 발생한다.
• 이러한 프로세스들이 페이지 스왑인, 스왑아웃을 위해 페이징 장치를 사용해야한다.
• 페이징 장치에 대한 큐잉이 진행되며, 준비 큐는 비게 된다.
• 프로세스들이 페이징 장치를 기다리는 동안 CPU 이용률은 떨어진다.
• 그럼 처음 상황이 다시 반복되게 된다.
• 결과적으로 스래싱이 발생해, 시스템 처리율은 대단히 낮아지고, 페이지 폴트는 상당히 늘어난다.
  실질 메모리 접근 시간은 증가하고, 프로세스들은 페이징 하는데 시간을 다 소비해 다른 일을 할 수 없게 된다.

 

메모리 압축

---

수정된 프레임을 스왑 공간으로 페이징하지 않고, 여러 프레임을 하나의 프레임으로 압축하는 방법이다.
이러면 시스템이 페이지 스와핑에 의존하지 않고, 메모리 사용량을 줄일 수 있다.