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

CS/운영체제

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

개발자딥게 2022. 8. 20. 12:02

1. 요구 페이징

요구 페이징 (Demand paging)

가상 메모리는 요구 페이징 방식으로 구현되며, 또한 세그멘테이션이나 페이지된 세그멘테이션 기법을 사용하기도 한다.

요구 페이징은 초기에 필요한 것들만 메모리에 적재하는 전략으로, 요구 페이징을 사용하는 가상메모리에서는 페이지들이 실행과정에서 실제로 필요해질 때 적재되는 방식이다. 즉, 한번도 접근되지 않는 페이지는 물리메모리에 전혀 적재되지 않는다.

요구 페이징 시스템의 중요사안

- 프레임 할당: 한정된 메모리에 어떤 프레임(프로세스의 단위, 페이지)을 올려야 좋을까?

- 페이지 교체 알고리즘: 모든 메모리에 프레임이 꽉 찼을 때, 어떤 프레임을 빼서 다른 프레임을 넣을까?

페이저(Pager)

프로세스 내의 개별 페이지를 관리한다. 그리고 실제로 어떤 페이지들이 사용될 것인지 추측한다.

프로세스 전체를 스왑인(swap-in: 메모리로 읽어들인다)하는 대신에 실제 필요한 페이지들만 메모리로 읽어 온다.

사용되지 않을 페이지는 메모리로 가져오지 않음으로써 시간낭비와 메모리 공간의 낭비를 줄일 수 있다.

유효-무효 비트(valid-invalid bit)

어느 페이지가 디스크에 있고, 어느 페이지가 메모리에 올라와 있는지 구별할 필요가 있는데, 이를 유효-무표 비트를 통해 알 수 있다. 이 비트가 유효하다고 설정되면, 해당 페이지가 메모리에 있다는 의미이고, 무효하다고 설정되면 해당 페이지가 유효하지 않거나 유효해도 디스크에 존재한다는 의미이다.

즉, 메모리에 올라오는 페이지에 대해서는 유효로 설정하며, 현재 메모리에 올라와 있지 않은 페이지의 페이지테이블 항목은 무효로 설정하거나, 그 페이지가 저장되어 있는 디스크 주소를 기록해둔다.

2. 페이지 부재

페이지 부재(Page Fault)

프로세스가 메모리에 올라와 있지 않는 페이지에 접근하려고 하면 페이지 부재 트랩(Page-Fault Trap)이 발생한다. 페이징 하드웨어는 페이지 테이블을 이용한 주소 변환 과정에서 무효 비트를 발견하고, 운영체제에게 트랩을 건ㄴ다. 이 트랩은 운영체제가 적재하지 않은 페이지 중에 필요한 페이지가 있기 때문이다.

페이지 부재 처리 과정

1. 프로세스에 대한 내부 테이블을 검사해서 그 메모리가 유효인지 무효인지 파악한다.

2. 만약 무효한 페이지라면 그 프로세스는 중단된다. 만약 유효한 참조인데 페이지가 아직 메모리에 올라오지 않았다면 디스크에 접근하여 해당 페이지를 메모리로 가져온다.

3. 빈공간 (Free Frame)을 찾는다.

4. 디스크에 새로이 할당된 프레임으로 해당 페이지를 읽어들이도록 요청한다.

5. 디스크 읽기가 끝나면 이 페이지가 이제는 메모리에 있다는 것을 알리기 위해 페이지 테이블을 갱신하며, 프로세스가 유지하고 있는 내부 테이블을 수정한다.

5. 트랩에 의해 중단되었던 명령어를 다시 실행한다. 프로세스는 마치 그 페이지가 항상 메모리에 있었던 것처럼 해당 페이지에 접근할 수 있다.

3. 페이지 교체 알고리즘

페이지 교체 (Page Replacement)

운영체제는 사용자 프로세스가 실행 중에 페이지 부재가 발생한다. 운영체제가 필요한 페이지가 디스크 어디에 위치하고 있는지 알아내지만, 빈 프레임이 없을 수 있다. 즉 모든 메모리가 사용 중인 경우가 있을 수 있다.

이때 페이지 교체가 발생한다. 즉 기존에 메모리에 올라가 있는 페이지를 빼고, 새롭게 필요로하는 페이지를 저장한다.

페이지 교체 과정

1. 디스크에서 필요한 페이지의 위치를 찾아낸다.

2. 빈 페이지 프레임을 찾는다.

2-1. 만약 빈 프레임이 있다면 그것을 사용한다.

2-2. 없다면 희생 프레임 victim frame을 선정하기 위해 페이지 교체 알고리즘을 가동시킨다.

2-3. 희생될 페이지를 디스크에 기록하고, 관련 테이블을 수정한다.

3. 새롭게 비워진 프레임에 새 페이지를 읽어오고 프레임 테이블을 수정한다.

4. 사용자 프로세스를 재시작한다.

페이지 교체 알고리즘 (Page Replacement Algorithms)

운영체제는 페이지 부재율(page-fault rate)가 가장 낮은 교체 알고리즘을 선정한다.

1. FIFO 페이지 교체: 메모리가 적재된 시간을 기록한 뒤, 메모리에 올라온 기간이 가장 오래된 페이지를 제거한다.

2. 최적 페이지 교체: 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체한다. 하지만 예측이 어렵다는 단점이 있다.

3. LRU 페이지 교체: 페이지 별 마지막 사용시간을 기록한 뒤, 최근에 가장 사용되지 않은 페이지를 교체한다.

4. LRU 근사 페이지 교체: LRU 페이지 교체를 지원하지 못하는 시스템이 있을 수 있다. 이때 참조비트 하나를 설정하여 어떤 페이지가 사용된 적이 있는지(1) 없는지(0) 정도는 파악하게 하는 알고리즘이다.

5. LFU 페이지 교체: Least Frequently Used, 참조 횟수가 가장 작은 페이지를 교체하는 방법.

6. MFU 페이지 교체: Most Frequently Used, 가장 작은 참조횟수를 가진 페이지는 최근에 적재된 페이지이므로, 앞으로 계속 사용될 것이라 판단한다.

4. 프레임 할당

프레임의 할당 (Allocation of Frames)

128KB 메모리 내에 1KB의 프레임이 128개 있다. 이 중 운영체제가 35KB를 차지하므로 가용 프레임은 총 93개이다.

처음부터 93번까지는 페이지 부재가 발생하면 빈 가용프레임을 사용한다. 94번째 페이지부재부터는 이미 사용한 93개의 프레임 중에서 하나를 선택해 페이지를 교체해야 한다. 프로세스가 종료되면 93개의 프레임은 가용프레임으로 반환된다.

"93개의 가용 프레임이 있고 프로세스는 2개가 있다. 각 프로세스에게 몇 프레임씩 할당할 것인가?"

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

최소한의 프레임을 할당해야 하는 이유는 성능과 관계가 있다. 할당되는 프레임의 수가 적으면 페이지 부재가 빈번하고 그러면 프로세스 실행이 늦어지기 때문이다. 또한 하나의 명령을 실행 중에 페이지 부재가 발생하면 그 명령은 처음부터 다시 시작되어야 하기 때문에 적어도 하나의 명령어가 참조하는 모든 페이지를 적재할 수 있는 최소의 프레임은 필수다.

할당 알고리즘 (Allocation Algorithms)

1. 균등 할당(equal allocation)

m개의 프레임을 n개의 프로세스에게 할당하는 가장 쉬운 방법으로, m/n개씩 똑같이 할당해 주는 것이다.

2. 비례 할당 (proportional allocation)

프로세스마다 요구하는 메모리 크기가 다르다는 점을 감안하여, 가용 메모리를 각 프로세스의 크기에 비례하여 할당하는 방법이다.

3. 전역교체/지역교체:

전역 교체란, 페이지 부재가 발생해서 victim page를 찾을 때 다른 프로세스에게 할당되었던 페이지까지 찾는 경우다. 우선순위가 낮은 프로세스를 희생시켜 우선순위가 높은 프로세스가 더 많은 프레임을 할당 받을 수 있게 해준다.

지역 교체에서는 프로세스에 할당된 프레임의 수는 변하지 않는다.

5. 쓰레싱 (Thrashing)

쓰레싱 (Thrashing)

할당된 프레임이 적은 프로세스는 페이지 부재가 빈번하게 발생한다.

페이지 교체가 필요하지만 이미 활발하게 사용되는 페이지들로만 이루어져 있어서 어떤 페이지가 교체되든 바로 다시 교체가 필요해진다. 과도한 페이징 작업을 쓰레싱이라고 부른다. 즉, 어떤 프로세스가 실행보다 페이징 작업에 더 많은 시간을 쓰고 있는 경우 쓰레싱이 발생했다고 한다.

쓰레싱 발생하는 과정

- 운영체제는 CPU 이용률을 감시하며, CPU이용률이 낮아지면 새로운 프로세스를 추가해 다중 프로그래밍 정도를 늘린다.

- 한정된 프레임을 여러 프로세스들이 사용하며 페이지 부재가 빈번해진다.

- 따라서 프로세스들은 페이징 장치를 기다리고, 그동안 CPU 이용률은 점차 떨어진다.

- 이를 본 운영체제는 CPU 이용률을 늘리기 위해 프로세스를 더 늘린다.

- 시스템 처리율은 매우 낮아지고 페이지 부재는 엄청 늘어나, 쓰레싱이 발행하게 된다.

쓰레싱 해결책

쓰레싱 현상을 방지하기 위해서는 각 프로세스가 필요로 하는 개수만큼 프레임을 할당해야 한다. 그너라 각 프로세스가 필요로 하는 프레임 수를 어떻게 알 수 있는가? 작업 집합 모델을 이용해 실제로 사용하고 있는 프레임의 수가 몇개인지 알아보는 방법이 있다.

작업 집합 모델 (Workin-Set Model)

구간을 정하여 최근 x번의 페이지 참조를 관찰한다. 한 프로세스가 x번 페이지를 참조했다면 그 안에 들어있는 서로 다른 페이지들의 집합을 작업집합(working set)이라고 부른다. 이 안에는 활발하게 사용되던 페이지들이 들어있다.

더이상 사용되지 않는 페이지들은 마지막 참조로부터 x번의 페이지 참조 후에는 이 집합에서 제외된다.

이로 인해 작업집합은 프로그램의 지역성에 근사하게 된다.

작업집합의 정확도는 x의 선택에 따라 좌우된다. x가 너무 작으면 전체 지역을 포함하지 못할 것이고, 너무 크면 여러 지역성을 과도하게 포함할 것이다.