- 가상 메모리를 통해서 물리 메모리보다 큰 프로세스를 실행 할 수 있지만,
- 그럼에도 물리 메모리의 크기는 한정되어있다.
가상 메모리의 물리 메모리는 한정되어 있어서 운영체제는 두가지를 결정할 수 있어야 함
→ 기존에 적재된 불필요한 페이지를 선별해 보조기억장치로 내보내고,
→ 프로세스들에게 적절한 수의 프레임을 할당해야한다.
요구 페이징(demand paging)
- 처음부터 모든 페이즈를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 기법
- 요구되는 페이지만 적재하는 기법
🗣️ [요구페이징 양상]
1. CPU가 특정 페이지에 접근한는 명령어를 실행한다.
2. 해당 페이지가 현재 메모리에 있을 경우(유효 비트가 1일 경우) CPU는 페이지가 적재된 프레임에 접근한다.
3. 해당 페이지가 현재 메모리에 없을 경우(유효 비트가 0일 경우) 페이지 폴트가 발생한다.
4. 페이지 폴트 처리 루틴은 해당 페이지를 메모리에 적재하고 유효비트를 1로 설정한다.
5. 다시 1번을 수행한다.
페이지 폴트(Page fault)
- 페이지 폴트가 자주 발생하는 이유?
- 나쁜페이지 교체 알고리즘을 사용해서
- 프로세스가 사용할 수 있는프레임자체가 적어서페이지 폴트(Page Fault)
가상 메모리(Virtual Memory) 시스템에서 발생하는 현상으로, 프로세스가 실행 중인 동안 필요한 데이터나 명령을 물리 메모리(실제 메모리)에 찾을 수 없어서 발생하는 상황을 나타낸다.
페이지 교체 알고리즘
좋은 페이지 교체 알고리즘은 ?
- 페이지 폴트가 적은 알고리즘
- 페이지 폴트가 발생하면 보조기억장치에 접근해야 해서 성능이 저하하기 때문이다.
페이지 폴트 횟수는 어떻게 알 수 있을까 ?
- 페이지 참조열(page reference String)
- CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열
페이지 참조열은 아래처럼 연속된 페이지를 생략한 것이 된다.
☑️ FIFO(First In First Out) 페이지 교체 알고리즘
: 메모리에 가장 먼저 올라온 페이지부터 나가는 방식
위 과정은 페이지 교체에서만 발생한 페이지 폴트만 간주한다. (초기에 적재될때 발생할 수 있는 페이지 폴트는 고려하지 않았다!)
장점
- 구현이 자체가 간단하다.
단점
- 프로그램 실행 초기에 잠깐 실행될 페이지도 있을 수 있지만, 프로그램 실행 내내 사용될 페이지의 경우에 먼저 적재되었다고 내보내면 안된다.
- 성능면에서 그렇게 좋은 방식은 아니다.
FIFO 페이지 교체 알고리즘 - 보완책
→ ☑️ [2차 기회(second - chance) 페이지 교체 알고리즘] → 참조비트로 기회를 줌
- 참조 비트 1: CPU가 한 번 참조한 적이 있는 페이지 → 바로 내쫓지 않고 참조 비트를 0으로 초기화 후 적재시간을 현재시간으로 설정
- 참조 비트 0: CPU가 참조한 적이 없는 페이지 → 가장 메모리가 오랫동안 머물렀음에도 CPU가 참조를 안했으므로 내쫓음
☑️ 최적 페이지 교체 알고리즘
- CPU가 참조하는 횟수를 고려한 알고리즘이다.
- 메모리에 오래 남아야 할 페이지는 자주 사용될 페이지
- 메모리에 없어도 될 페이지는 오랫동안 사용되지 않을 페이지
⇒ 즉, 앞으로 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘
⇒ 페이지 폴트의 빈도가 FIFO에 비해 줄었음
장점
가장 낮은 페이지 폴트율을 보장하는 페이지 교체 알고리즘
단점
- 실제 구현이 어렵다.
- 앞으로 오랫동안 사용되지 않을 페이지를 예측하기 어려움
⇒ 즉,예측이 어렵기 때문에 최적 페이지 교체 알고리즘은 다른 페이지 교체 알고리즘 성능을 평가하기 위한 하하선 기준으로 간주한다.
☑️ LRU(Least-Recently-Used) 페이지 교체 알고리즘
- 최적 페이지 교체 알고리즘 : 가장 오래 사용되지 않을 페이지 교체 (미래 예측)
- LRU 페이지 교체 알고리즘 : 가장 오래 사용되지 않은 페이지 교체 (과거 고찰)
- “최근에 사용되지 않는 페이지는 앞으로도 사용안되지 않나 ?”라는 관점에서의 알고리즘
☑️ LFU(Least Frequently Used) 페이지 교체 알고리즘
- LFU 알고리즘은 참조횟수가 가장 적은 페이지를 교체하는 알고리즘이다.
- 교체 대상이 여러 개라면 가장 오랫동안 사용하지 않은 페이지를 교체한다.
☑️ MFU(Most Frequently User) 페이지 교체 알고리즘
- MFU 알고리즘은 LFU와 반대로 참조 횟수가 가장 많은 페이지를 교체하는 알고리즘이다.
→ “가장 많이 사용되었기 때문에 앞으로 안쓰지 않을까?” 라는 관점에서의 알고리즘
☑️ **클럭 알고리즘 (NRU or NUR)**
- 클럭 알고리즘은 하드웨어적인 자원을 통해 기존(LRU, LFU)알고리즘의 소프트웨어적인 운영 오버헤드를 줄인 방식입니다.
- NRU(Not Used Recently) 또는 NUR(Not Recently Used) 알고리즘이라고도 부르기도 합니다.
- 클럭 알고리즘은 LRU처럼 가장 최근에 참조되지 않은 페이지를 대상으로 선정한다는 점에서 LRU와 근사하지만 교체되는 페이지의 참조 시점이 가장 오래되었다는 것을 보장하지는 않는다.
- 프레임 내의 페이지가 참조될 때 하드웨어에 의해 1로 자동 세팅됩니다.
- 클럭 알고리즘은 한 바퀴 돌며 참조되지 않은 페이지의 참조 비트 값을 0으로 바꾼 후 지나갑니다.
- 참조 비트가 0인 페이지를 방문하면 해당 페이지를 교체합니다.
즉, 페이지가 참조되어 1이 되고, 한 바퀴 도는 동안 사용되지 않으면 0이 되고 다시 한 바퀴를 도는 동안 사용되지 않는 페이지는 참조되지 않았으므로 교체 대상 페이지로 선정하는 알고리즘입니다.
클럭 알고리즘은 시계 바늘이 한 바퀴 도는 동안 걸리는 시간만큼 페이지를 메모리에 유지시켜 페이지 부재율을 줄이도록 설계 되었다. 때문에 클럭 알고리즘을 2차 기회 알고리즘이라 부르기도 한다.
스래싱과 프레임 할당
스래싱 (Thrashing) 이란 ?
개념: 너무 자주 페이지 교체가 일어나는 현상으로 어떤 프로세스에 지속적으로 페이지 부재가 발생하여 프로세스의 처리시간보다 페이지 교체시간이 더 많이 발생하는 현상이다
- 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능(CPU 이용률)이 저하되는 문제를 스래싱이라고 한다.
- 주 기억장치(메모리)가 과도하게 활용되어 페이지 폴트(Page Fault)가 지속적으로 발생하면서 시스템 성능이 급격하게 저하되는 현상
스래싱
- 동시 실행되는 프로세스 수(멀티프로그래밍 정도)를 늘린다고 CPU이용률이 높아지는 것은 아니다.
스래싱 문제 정리
멀티 프로그래밍 수가 증가하면 CPU가
Maximization할 수 있지만, 일정 수를 초과하면 스래싱이 발생해버린다.(CPU이용률 오히려 저하됨)
스레싱이 발생하는 이유?
- 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문이다.
⇒ 따라서 운영체제(OS) 는 최소한의 프레임 수를 파악하고 프로세스들에게 적절하게 프레임을 할당해 줄 수 있어야 한다.
프레임
:가상메모리의 물리메모리를 고정된 크기로 쪼갠 것
페이지
:프로세스를 고정된 크기로 쪼갠 것
프레임 할당 방식 2가지
☑️ 1) 정적할당 방식
균등할당, 비례할당 ⇒ 프로세스 실행 과정 고려 x, 프로세스 크기나 물리메모리 크기만 고려함
1. 균등 할당(equal allocation)
- 가장 단순한 할당방식
- 모든 프로세스들에게 균등하게 프레임 할당
2. 비례 할당(proportional allocation)
- 프로세스의 크기를 고려하자
- 프로세스 크기에 비례하여 프레임할당
☑️ 2) 동적할당 방식
: 하나의 프로세스가 실제로 얼마나 많은 프레임이 필요할지를 보고 (즉, 실행 과정을 관찰하면서 판단하는 방식)
1. 작업 집합 모델 기반 할당 방식
: 프로세스가 일정 기간 동안 참조한 페이지 집합을 기억하여 빈번한 페이지 교체를 방지(스래싱 방지)하는 방식
- 프로세스가 실행하는 과정에서 배분할 프레임 결정
- 스래싱이 발생하는 이유는 빈번한 페이지 교체 때문임
⇒ 그렇다면 CPU가 특정 시간 동안 주로 참조한 페이지 개수만큼만 프레임에 할당하면 된다.
2. 페이지 폴트 빈도 기반 할당 방식(PFF)
2개의 가정에서 생겨난 아이디어
- 페이지 폴트율이 너무 높으면 그 프로세스는 너무 적은 프레임을 갖고 있다.
- 페이지 폴트율이 너무 낮으면 그 프로세스는 너무 많은 프레임을 갖고 있다.
⇒ 상한선, 하한선으로 프레임 할당 여부를 정함
1. Global VS Local Replacement
- Global Replacement
- 메모리 상의 모든 프로세스 페이지에 대한 교체 작업을 수행한다.
- 앞에서 배운 FIFO, OPT, LRU 등은 Victim을 정할 때, 모든 메모리에 올려져 있는 frame을 다 확인 후에 교체를 수행했다.
- Local Replacement
- 메모리 상의 자기 자신의 프로세스 페이지에 대해서만 교체 작업을 수행한다.
- 지금 요청이 들어온 page가 p1이라면, 메모리상에 올라가 있는 frame 중 p1 frame만 교체의 대상으로 간주한다.
메모리 사용 효율은 일반적으로 Global Replacement가 좋다.
- 정적 할당 (Static Allocation):
- 정적 할당은 프로그램 실행 전에 메모리를 할당하는 방식입니다. 할당된 메모리는 프로그램의 전체 수명 동안 사용됩니다.(정적할당 방식은 크기와 수명이 고정)
- 장점:
- 메모리 할당과 해제에 따른 오버헤드가 적습니다.
- 실행 시간에 동적으로 메모리를 할당하거나 해제할 필요가 없어서 빠른 실행 속도를 가질 수 있습니다.
- 단점:
- 정적으로 할당된 메모리는 프로그램이 실행되는 동안 계속 사용되므로, 프로그램이 필요로 하는 메모리의 크기를 정확하게 예측하여 할당해야 합니다. 메모리 부족 문제가 발생할 수 있습니다.
- 메모리 낭비가 발생할 수 있습니다. 프로그램이 실행되는 동안 사용하지 않는 메모리도 계속 할당되어 있기 때문입니다.
- 동적 할당 (Dynamic Allocation):
- 동적 할당은 프로그램 실행 중에 필요에 따라 메모리를 동적으로 할당하는 방식입니다. 메모리는 필요할 때 할당되고, 사용이 끝나면 해제됩니다.
- 장점:
- 메모리 사용을 유연하게 조정할 수 있습니다. 필요한 만큼의 메모리만 할당하여 메모리를 효율적으로 사용할 수 있습니다.
- 실행 시간에 동적으로 메모리를 할당하고 해제하기 때문에, 메모리를 유연하게 관리할 수 있습니다.
- 단점:
- 메모리 할당과 해제에 따른 오버헤드가 발생합니다. 메모리를 동적으로 할당하고 해제하는 과정에 시간이 걸립니다.
- 잘못된 사용으로 인해 메모리 누수 (memory leak)가 발생할 수 있습니다.
