[OSTEP] I. 가상화

[4장. 프로세스의 개념]

 

프로세스: 실행 중인 프로그램

 

OS는 시분할 기법을 통해 CPU를 가상화시킨다. 시분할 기법은 CPU를 공유하기 때문에 각 프로세스의 성능은 낮아진다.

CPU 가상화의 효율적인 구현을 위해서는 도구(메커니즘)와 지능(정책)이 필요하다.

*정책: OS에서 어떤 결정을 내리는 데 사용하는 알고리즘

 

프로세스의 하드웨어 상태 중 가장 중요한 구성 요소는 메모리이다.

 

프로세스 생성

프로그램 코드와 정적 데이터를 메모리, 프로세스의 주소 공간에 load한다. 이후 스택과 힙을 생성하고 초기화 하고 입출력 셋업과 관계된 다른 작업을 마치게 되면 OS는 프로그램 실행을 위한 준비를 마치게 된다.

 

프로세스 상태

• 실행: 프로세스가 명령어를 실행중인 상태
• 준비: 프로세스가 실행할 준비가 되어있지만 OS가 다른 프로세스를 실행중인 등의 이유로 대기 중인 상태
• 대기: 프로세스가 다른 사건을 기다리는 동안 프로세스의 수행을 중단시키는 연산 (예: 입출력 요청)

운영체제의 스케줄링 정책에 따라 실행과 준비 상태를 전이한다.

 

자료구조

OS는 프로세스 리스트, 레지스터 문맥 등의 자료구조가 있다.

프로세스 리스트는 시스템에 존재하는 모든 프로세스에 대한 정보를 갖고 있고 각 노드는 프로세스 제어 블록(PCB)이다.

 

[5장. 막간: 프로세스 API]

 

fork() 시스템 콜

프로세스 생성에 사용된다. 생성 성공시 0을 반환한다. 새로 생성된 프로세스는 자식 프로세스가 된다. 자식과 부모 프로세스는 완전히 동일하지는 않고 각자 주소공간, 레지스터, PC값을 따로 가진다.

 

wait() 시스템 콜

부모 프로세스가 자식 프로세스의 종료를 대기해야 하는 경우도 발생할 수 있다. wait() 시스템 콜은 자식 프로세스가 종료될 때까지 리턴하지 않는다.

 

exec() 시스템 콜

자기 자신이 아닌 다른 프로그램을 실행해야 할 때 사용한다. fork는 복사본, exec는 다른 프로그램이다.

 

[6장. 제한적 직접 실행 원리(Limited Direct Execution)]

 

시분할 시스템을 이용한 CPU 가상화 구현에는 성능 저하와 제어 문제를 해결해야 한다. 특히 제어 문제가 중요하다.

 

기본 원리

프로그램을 CPU 상에서 직접 실행시키는 것이다. 빠르게 실행된다는 장점이 있다.

문제점

 

제한된 연산: 사용자 모드와 커널 모드를 도입하여 프로세스가 할 수 있는 일을 제한한다. 제한된 작업의 실행을 허용하기 위해 시스템 콜이 제공된다. 시스템 콜을 실행하기 위해 프로그램은 trap 특수 명령어를 실행해야 한다. trap을 통해 커널 모드로 진입하여 프로세스가 요청한 작업을 처리한 후에 return-from-trap을 통해 사용자 모드로 돌아온다.

 

프로세스 간 전환

협조 방식: 시스템 콜 호출시 까지 대기.

협조 방식을 사용하는 OS는 yield 시스템 콜을 제공한다. 이 시스템 콜을 통해 OS가 CPU를 다른 프로세스에게 할당할 수 있는 기회를 제공한다. 협조 방식의 스케줄링 시스템은 근본적으로 수동적이다. 프로세스가 무한 루프에 빠져 시스템 콜을 호출할 수 없다면 문제가 발생할 수 있다.

 

비협조 방식: OS가 제어권 확보

시스템 콜이 없더라도 OS에게 제어권을 넘기려면 타이머 인터럽트를 이용하면 된다. 타이머는 인터럽트를 주기적으로 발생시키며 인터럽트가 발생하면 처리하는 과정에서 제어권이 자연스럽게 OS에게 넘어오게 된다.

 

문맥의 저장과 복원

어떤 방식으로든 OS가 제어권을 다시 획득하면 현재 실행중인 프로세스를 계속 실행할 것인지 아니면 다른 프로세스로 전환할 것인지를 스케줄러에 의해 결정해야 한다.

현재 실행중인 프로세스를 중단하고 다른 프로세스를 실행하기로 결정했다면 OS는 문맥 교환(context switching) 코드를 실행시킨다. 현재 실행중인 프로세스의 레지스터 값들을 저장하고 새로 실행될 프로세스의 레지스터 값을 복원하는 것이다.

 

[7장. 스케줄링 : 개요]

 

작업의 반환 시간 기준

• FIFO: 단순하고 구현하기 쉽다. CPU를 많이 필요로 하지 않는 프로세스들이 CPU를 오랫동안 사용하는 프로세스가 끝날때 까지 기다리기 때문에(convoy effect) 이런 경우 평균 반환시간이 급격하게 늘어난다.
• 최단 작업 우선(SJF): 가장 짧은 실행 시간을 가진 작업을 먼저 실행시키기 때문에 convoy effect를 해결할 수 있다. 모든 작업이 동시에 도착한다면 SJF가 최적의 스케줄링 알고리즘임을 증명할 수 있다. 하지만 동시에 도착하지 않고 실행시간이 긴 작업이 먼저 실행되는 도중 짧은 작업들이 도착해도 앞의 작업을 기다릴수밖에 없기때문에 convoy effect가 다시 발생하게 된다.
• 최소 잔여시간 우선(STCF): SJF에 선점 기능을 추가했다. 새로운 작업이 도착하면 현재 실행중인 작업의 잔여 실행 시간과 새로운 작업의 잔여 실행 시간을 비교하여 작은 쪽의 작업을 스케줄한다.

 

작업의 응답 시간 기준

• 라운드 로빈(RR): 작업이 끝날때까지 기다리지 않고 일정 시간 실행한 후 실행 큐의 다음 작업으로 전환한다. 타임 슬라이스의 길이는 타이머 인터럽트의 배수여야 한다. 타임 슬라이스의 길이가 짧을수록 응답 시간은 짧아지지만 문맥 교환이 그만큼 잦게 일어나서 성능 하락이 발생한다. 반환 시간만을 기준으로 삼을 경우 RR을 포함한 공정한 정책은 반환 시간이 좋지 않다.

 

프로세스가 입출력 요청으로 인해 대기 상태가 되는 경우 다른 프로세스가 CPU를 사용하여 연산을 중첩하면 시스템 사용률을 향상시킬 수 있다.

반환 시간과 응답 시간 중 하나를 최적화 하면 나머지 하나는 좋지 않은 특성을 나타낸다.

 

[8장. 스케줄링: 멀티 레벨 피드백 큐]

 

MLFQ가 해결하고자 하는 기본적인 문제는 두가지이다.

• 짧은 작업을 먼저 실행시켜 반환 시간을 최적화하고자 한다
• 응답시간을 최적화한다

 

MLFQ는 여러개의 큐로 구성되며 각각 다른 우선순위가 배정되고 실행 준비가 된 프로세스는 이 중 하나의 큐에 존재한다. 큐에 둘 이상의 작업이 존재할 수 있으며 같은 우선순위를 가지고 이 작업들 사이에는 RR 알고리즘이 사용된다.

MLFQ의 핵심은 우선순위를 정하는 방식이다.

기본 규칙은 우선순위가 높은 작업이 실행되고 우선순위가 같다면 RR 방식으로 실행된다.

스케줄러는 작업의 길이를 알 수 없기 때문에 일단 짧은 작업이라고 가정하여 높은 우선순위를 부여한다. 정말로 짧은 작업이면 금방 종료될것이고 긴 작업이라면 천천히 아래 큐로 이동하기 때문에 스스로 긴 배치형 작업이라는 것을 증명하게 되어서 MLFQ는 SJF를 근사할 수 있다.

 

현재 MLFQ의 문제점

• 기아 상태가 발생할 수 있다.
• 사용자가 스케줄러를 자신에게 유리하도록 동작시킬 수 있다.
• 프로그램은 시간 흐름에 따라 특성이 변할수 있지만 현재 상태로는 반영하지 못한다.

일정 시간마다 우선순위를 일괄적으로 상향 조정하면 기아 상태와 변경된 특성에 적합한 스케줄링 방법을 적용할 수 있다. 하지만 적절한 일정 시간을 결정하는것은 매우 어렵다.

MLFQ의 각 단계에서 CPU 총 사용 시간을 측정하면 스케줄러를 자신에게 유리하게 동작시킬 수 있는 문제까지 막을 수 있다.

 

요약

우선순위가 높은 작업이 실행된다.

우선순위가 같으면 해당 작업들은 RR 방식으로 실행된다.

작업이 시스템에 들어가면 최상위 큐에 배치된다.

작업이 지정된 단계에서 배정받은 시간을 소진하면 작업의 우선순위는 한 단계 감소한다.

일정 주기가 지난 후 시스템의 모든 작업을 최상위 큐로 이동시킨다.

작업의 특성에 대한 정보 없이 작업의 실행을 관찰하여 생긴 과거 기록들을 토대로 우선순위를 지정한다.

 

[9장. 스케줄링: 비례 배분]

 

반환 시간이나 응답 시간을 최적화하는 대신 프로세스들에게 CPU의 일정 비율을 보장하는 것이 목적이다.

추첨권 이라는 무작위성 개념이 근간을 이룬다.

 

추첨 기법

• 추첨권 화폐: 사용자가 추첨권을 자신의 화폐 가치로 추천권을 자유롭게 할당할 수 있도록 허용한다.
• 추천권 양도: 일시적으로 다른 프로세스에게 추첨권을 넘겨줄 수 있다.
• 추첨권 팽창: 일시적으로 자신이 소유한 추첨권의 수를 늘이거나 줄일 수 있다. 프로세스들이 상호 경쟁하는 상황에서는 의미가 없다.

구현이 매우 단순하다는 장점이 있다. 정렬 순서는 알고리즘의 정확성에 영향을 주지는 않지만 정렬된 경우 검색 횟수가 최소화되는 것을 보장한다.

 

무작위성을 이용하면 단순하게 만들 수 있지만 정확한 비율을 보장할 수 없다.

결정론적 공정 배분 스케줄러인 보폭 스케줄링을 이용한다.

 

리눅스 CFS(Completely Fair Scheduler)

효율성과 확장성이라는 장점을 가지고 있다. (추가내용들은 우선 생략)

 

[10장. 멀티프로세서 스케줄링 (고급)]

 

응용 프로그램을 병렬로 작성할 때 쓰레드를 이용한다.

캐시는 시간적 지역성과 공간적 지역성에 기반을 둔다.

 

단일 큐 멀티프로세서 스케줄링(SQMS): 단순함이 장점이다. 확장성과 캐시 친화성에 문제가 있다. 캐시 진화성은 SQMS 스케줄러가 가능한 한 프로세스가 동일한 CPU에서 재실행될 수 있도록 시도한다.

 

멀티 큐 멀티프로세서 스케줄링(MQMS): 일부 시스템은 멀티 큐로 둔다. 확장성이 좋다. CPU 개수가 증가할수록 큐의 개수도 증가하므로 락과 캐시 경합이 더이상 문제가 되지 않는다. 하지만 워크로드의 불균형이 발생한다. 지속적인 이주를 통해 해결할 수 있고 이주 필요 여부는 작업 훔치기라는 기술을 통해 결정한다.

 

[13장. 주소 공간의 개념]

 

여러 프로그램이 메모리에 동시에 존재하려면 보호가 중요한 문제가 된다.

 

주소 공간

주소 공간은 실행 프로그램의 모든 메모리 상태를 갖고 있다.

메모리 가상화: 물리 메모리를 공유하는 다수의 프로세스에게 프로세스 전용의 커다란 주소 공간이라는 개념을 제공하는 것

 

가상 메모리 시스템(VM)의 주요 목표

• 투명성(transparency): OS는 프로세스가 가상 메모리의 존재를 인지하지 못하도록 구현 해야한다.
• 효율성(efficiency): OS는 가상화가 시간과 공간 측면에서 효율적이도록 해야한다.
• 보호(protection): OS는 프로세스를 자신 및 다른 프로세스들로부터 보호해야 한다.

 

[15장. 주소 변환의 원리]

 

주소 변환: 가상 주소를 물리 주소로 변환하는 것

 

동적(하드웨어 기반) 재배치

각 CPU마다 베이스와 바운드(한계)라는 2개의 하드웨어 레지스터를 사용한다.

물리 주소 = 가상 주소 + 베이스

바운드는 프로세스가 생성한 모든 주소가 합법적이고 프로세스의 범위 내에 있다는 것을 확인한다. 그렇지 않다면 예외를 발생시키고 예외 핸들러가 실행되도록 조치해야 한다.

주소 변환에 도움을 주는 프로세서의 일부를 메모리 관리 장치(MMU)라고 부르기도 한다.

 

운영체제 이슈

프로세스가 생성될 때 OS는 주소 공간이 저장될 메모리 공간을 찾아 조치를 취해야 한다.

프로세스가 종료될 때 메모리를 회수하여 다른 프로세스나 OS가 사용할 수 있게 해야 한다.

OS는 문맥 교환이 일어날 때도 몇 가지 추가 조치를 취해야 한다.

 

동적 재배치는 내부 단편화가 일어나서 비효율적이다.

 

[16장. 세그먼테이션]

 

세그먼테이션: 베이스/바운드의 일반화

MMU에 하나의 베이스와 바운드값이 존재하는게 아니라 세그먼트(코드, 스택, 힙)마다 베이스와 바운드 값이 존재한다.

가상 주소의 최상위 비트 몇 개를 세그먼트 종류를 나타내는 데 사용한다.

세그먼트 종류를 나타내는 데 최상위 2비트를 사용하고 세그먼트는 3종류만 존재하기 때문에 세그먼트 하나는 미사용으로 남게되어 전체 주소 공간의 1/4는 사용이 불가능하다.

 

스택

다른 세그먼트들과 다르게 반대 방향으로 확장된다.(LIFO) 다른 형식의 변환을 사용한다.

 

공유 지원

메모리를 절약하기 위해 주소 공간들 간에 특정 메모리 세그먼트를 공유하는 것이 유용하다. 특히, 코드 공유가 일반적이다. 공유를 지원하기 위해 세그먼트마다 protection bit를 추가하여 세그먼트를 읽거나 쓸 수 있는지, 혹은 세그먼트의 코드를 실행시킬 수 있는지 나타낸다. 코드 세그먼트를 읽기 전용으로 설정하면 주소 공간의 독립성을 유지하면서도 여러 프로세스가 주소 공간의 일부를 공유할 수 있다.

 

시스템이 각 주소 공간(세그먼트) 단위로 가상 주소 공간을 물리 메모리에 재배치하기 때문에 전체 주소 공간이 하나의 베이스-바운드 값을 갖는 방식에 비해 물리 메모리를 저장할 수 있다.

세그먼테이션 도입을 위해서 OS가 몇 가지 문제를 해결해야 한다.

• 문맥 교환
• 세그먼트 크기 변경
• 미사용 중인 물리 메모리 공간의 관리: 각 세그먼트의 크기가 다를 때 작은 공간들이 남아서 새로운 세그먼트에 할당하기도 힘들고 확장하는데도 도움이 되지 않는다.(=외부 단편화) 기존의 세그먼트를 정리하여 물리 메모리를 압축하는것이 하나의 해결책이다.

 

세그먼테이션에 필요한 연산은 쉽고 구현에도 적합하기 때문에 속도가 빠르다. 오버헤드도 최소이다. 하지만 세그먼트의 크기가 일정하지 않아서 외부 단편화가 발생하고 유연하지 않다.

 

[17장. 빈 공간 관리]

 

공간의 크기가 가변적인 경우(세그먼테이션) 빈 공간을 관리하기가 어렵다.

 

저수준 기법들

• 분할과 병합: 메모리 청크보다 큰 공간을 요청한 경우 요청이 실패하지만 더 작은 공간을 요청한 경우 공간을 분할하여 요청을 충족시킨다. 메모리 청크가 반환될 때 해제된 빈 공간이 기존에 존재하던 빈 공간과 인접한 경우 병합한다.
• 할당된 공간의 크기 파악
• 빈 공간 리스트 내장
• 힙의 확장: 힙의 공간을 모두 사용하면 OS에 더 많은 메모리를 요청한다.

 

기본 전략

• 최적 적합: 빈 공간 리스트를 탐색하여 요청한 크기와 같거나 더 큰 메모리 청크를 찾은 후 그 중에서 가장 작은 크기의 청크를 반환하여 사용한다. 공간의 낭비를 줄일 수 있지만 항상 완전탐색을 하기 때문에 성능이 저하된다.
• 최악 적합: 마찬가지로 완전탐색으로 인해 성능이 저하된다.
• 최초 적합: 요청보다 큰 첫번째 블럭을 찾아서 요청만큼 반환한다. 속도가 빠르다. 하지만 리스트의 앞쪽에 크기가 작은 블럭이 모여있다면 탐색 시간이 길어진다. 주소-기반 정렬을 사용하여 좀 더 효율적으로 관리할 수 있다.
• 다음 적합: 리스트의 처음부터 탐색하는 대신 마지막으로 찾은 원소를 가리키는 추가의 포인터를 유지한다.

 

다른 접근법

• 개별 리스트
• 버디 할당: 요청이 들어오면 크기에 맞는 공간이 될 때까지 반으로 계속 분할한다. 블럭히 해제될 때 2의 배수 버디가 비어있는지 확인하여 전체 빈 공간이 복원되거나 버디가 사용 중이라는 것이 밝혀질 때까지 재귀적으로 계속 병합해나간다.

 

위의 방식들은 확장성에 문제가 있다.

 

[18장. 페이징: 개요]

 

페이지: 프로세스의 주소 공간을 가변 크기인 논리 세그먼트로 분할한 것이 아닌 고정 크기의 단위로 나눈것.

페이지 테이블: 주소 공간의 가상 페이지 주소 변환 정보를 저장한다.

 

페이징을 사용하면 유연성과 빈 공간 관리의 단순함을 얻을 수 있다.

 

페이지 테이블이 메모리 상에서 너무 커지면 이로 인해 처리 속도가 저하될 수 있다.

 

[19장. 페이징: 더 빠른 변환(TLB)]

 

주소 변환을 빠르게 하기 위해 변환 색인 버퍼(translation lookaside buffer, TLB)를 도입한다. 일종의 페이지 테이블에서의 캐시라고 보면 된다. 가상 메모리 참조 시, TLB에 원하는 정보가 있는지 먼저 확인하고 있다면(hit) 페이지 테이블에 접근하지 않고 변환을 바로 수행한다.

 

*TLB를 포함한 캐싱은 시간적 지역성과 공간적 지역성에 기반을 두고 있다.

 

TLB 미스가 발생한 경우 페이지 테이블에 접근하여 변환 정보를 찾아야 한다.

 

문맥 교환시 TLB에 이전 프로세스가 사용한 VPN이 남는다. 문맥 교환이 발생할 때마다 TLB를 비우면 해결이 되지만 또 다른 문제들이 야기된다. 그래서 주소 공간 식별자(ASID) 필드를 추가하여 VPN이 같더라도 ASID로 올바른 주소 변환을 할 수 있다.

 

[20장. 페이징: 더 작은 테이블]  / 차후 추가공부 예정

 

페이지 테이블의 크기를 줄일 수 있는 간단한 방법은 페이지의 크기를 증가시키면 된다. 단점으로는 내부 단편화가 증가한다. 페이지 테이블의 크기는 줄었을지언정 오히려 메모리 고갈을 더 가속화 시키게 된다.

 

세그먼테이션-페이징 혼용

프로세스의 전체 주소 공간을 위해 하나의 페이지 테이블을 두는 대신 논리 세그먼트마다 따로 페이지 테이블을 둔다.

TLB 미스 발생시 세그먼트 비트를 사용해서 어떤 베이스와 바운드 쌍을 사용할지 결정한다.

 

멀티 레벨 페이지 테이블

세그먼테이션을 사용하지 않는 방법이다. 선형 페이지 테이블을 트리 구조로 표현한다.

페이지 테이블을 페이지 크기의 단위로 나누고 페이지 내의 valid 비트가 모두 0이면 할당하지 않는다. 페이지 디렉터리라는 자료 구조를 사용한다. PDE의 valid가 1이라면 해당 PDE가 가리키는 페이지가 최소 하나 이상의 PTE의 valid bit가 1이라는 의미이다.

사용된 주소 공간의 크기에 비례해서 페이지 테이블이 할당된다는 장점이 있다. 또한 메모리 관리가 용이하다.

하지만 TLB miss 발생시 주소 변환을 위해 두 번의 메모리 로드가 발생한다.(페이지 디렉터리와 PTE 접근 각 한번)

페이지 테이블의 크기를 줄인 대신 TLB miss시의 비용이 커진 셈이다.

 

[21장. 물리 메모리 크기의 극복: 메커니즘]

 

프로세스에게 굳이 큰 주소 공간을 제공하는 이유는 편리함과 사용 용이성이 좋기 때문이다.

 

스왑 공간: 디스크에 페이지들을 저장할 수 있는 일정 공간.

 

TLB hit가 되면 물리 주소를 얻고 메모리로 바로 가져온다.

TLB miss가 되면 PTBR를 사용하여 PTE를 추출한다. 해당 페이지 항목이 유효하고 관련 페이지가 물리 메모리에 존재하면 PFN 정보를 추출하여 TLB에 탑재시킨 후 명령어를 재실행하면 TLB hit가 된다.

하지만 이것은 모든 페이지가 물리 메모리에 존재할때의 가정이다.

 

PTE에 해당 페이지가 물리 메모리에 존재하지 않는다는 것을 표현하려면 present bit를 이용한다. 해당 비트가 1이라면 위의 메커니즘이 적용되고 만약 0이라면 페이지 부재(page fault)가 발생한다. 이 때, 페이지 부재를 처리하기 위해 제어권이 OS에 넘어가고 페이지 부재 핸들러가 실행된다.

 

페이지 부재 발생시 OS는 페이지 테이블에서 해당 페이지의 디스크 상 위치를 파악하여 스왑 공간으로부터 페이지를 가져와(page in) 메모리로 탑재시킨다.

page in을 할 때, 물리 메모리에 빈 공간이 없다면 기존 페이지를 스왑 공간으로 내보내야 한다.(page out)

이 과정을 교체라고 하고 교체할 페이지를 선택하는 것을 페이지 교체 정책이라고 한다.

교체가 완료되면 OS는 페이지 테이블을 갱신하고 명령어를 재시도한다. TLB miss가 발생하게 되고 한번 더 재시도를 하면 TLB hit가 된다.

 

TLB 미스 발생 시 세가지의 경우가 있다

• 페이지가 유효하고 존재하는 경우: TLB miss 핸들러가 PTE에서 PFN을 가져와 명령어를 재시도 한다.
• 페이지가 유효하지만 존재하지 않는 경우: 페이지 부재가 발생했기 때문에 페이지 부재 핸들러가 실행되어 처리한다.
• 페이지가 유효하지 않은 경우: OS의 트랩 핸들러에 의해 처리되도록 한다.

 

물리 메모리의 여유 공간이 고갈된 후에 교체 알고리즘이 작동하는 것은 그리 효율적이지 않다.

어느정도의 여유 공간을 가지고 있어야 하기 때문에 여유 공간의 크기가 최소값보다 작아지면 스왑 데몬(페이지 데몬)이라는 백그라운드 쓰레드를 실행하여 여유 공간의 크기가 최대값에 이를때까지 페이지를 제거한다.

다수의 페이지들을 클러스터나 그룹으로 묶어서 한번에 스왑 파티션에 저장하면(클러스터링) 오버헤드를 경감시켜서 디스크의 효율을 높일 수 있다.

 

[22장. 물리 메모리 크기의 극복: 정책]

 

메인 메모리는 가상 메모리의 페이지를 가져다 놓기 위한 캐시로 볼 수 있다.

페이지 교체 정책의 목표는 캐시 미스를 최소화 시키는 것이다.(페이지 부재 최소화) 한편으로는 캐시 히트를 최대화 하는 것도 목표라고 할 수 있다.

 

최적 교체 정책

가장 나중에 접근될 페이지를 교체하는것이 최적이라는 이론. 미래를 미리 알 수 없기 때문에 구현이 불가능하다. 다만 정책 수립시 비교 기준으로는 적합하다.

 

간단한 정책

• FIFO: 큐에 먼저 들어온 페이지가 먼저 교체된다. 구현이 매우 쉽지만 페이지의 중요도를 판단하지 않고 무조건 선입선출을 하기때문에 성능이 좋지 않다.
• 무작위: 구현이 매우 쉽지만 성능이 매번 다르다. 평균적으로는 FIFO보다 약간 좋다.

 

과거 이력 기반 알고리즘

지역성의 원칙에 기반을 두어서 빈도수와 최근성을 활용한다.

• LRU(least recently used): 가장 오래전에 사용된 페이지 교체. 최적 기법과 근사한 성능이다.
• LFU(least frequently used): 가장 적은 빈도로 사용된 페이지 교체

 

쓰래싱: 끊임없이 페이징이 발생하는 상황

 

[23장. 완전한 가상 메모리 시스템]