💻 필요성
한 프로그램 내에서도 자주 사용하는 부분과 그렇지 않은 부분이 존재한다.
그렇다면, 자주 사용치도 않는 부분까지 모두 메인 메모리에 올려놓을 필요가 있을까?
메모리는 디스크에 비해 값비싼 자원인데 이를 더 효율적으로 활용할 방안이 없을까?
라는 생각에서 나온것이 가상메모리 시스템이다.📖 가상메모리의 핵심
가상메모리 시스템은 다음 2가지에서 그 실마리를 잡게 되었다.
1. 프로세스의 모든 메모리 참조는 논리주소를 기준으로 이루어지며,
프로세스 수행 시간에 동적으로(런타임) 물리주소로 변환된다.
즉, 프로세스가 실행되고 스왑아웃 후 다시 스왑인 될때 이전과 다른주소에 적재될수가 있다.
2. 프로세스의 주소공간은 여러 블록(페이지,세그먼트)로 나뉘어 질수 있고 이 블록들은
메인메모리의 연속된 영역에 위치할 필요가 없다.
결국 위 조건에서 우리는 프로세스의 물리주소가 동적으로 실행될때 변환되며
메모리 상에 통으로 적재될 필요가 없다는 사실을 알수있다.
위 조건이 만족된다면 결국 프로세스의 모든 블록이 메인 메모리에 적재되있을 필요가 없다.
다음에 실행될 프로세스의 블록과
그에 대한 데이터만 존재한다면 약간의 시간 동안은 실행이 가능하다.
이를 통해 우리는 가상 메모리 시스템의 실마리를 잡을수가 있다.📖 장점
가상 메모리 시스템이란 결국 프로세스의 필요한 부분만 잘라서 메인 메모리에 적재하는것이다.
아직 적재 되지 않은 부분 참조시에는 인터럽트 발생후 해당 부분을 I/O 작업을 통해 가져온다.
이를 통해 우리는 다음과 같은 이점을 얻을수 있다.
1. 보다 많은 프로세스를 메인메모리에 적재할수 있다.
2. 메인메모리보다 큰 크기의 프로그램도 실행가능하다.📖 쓰레싱
가상메모리 시스템에서 해결해야할 문제중 하나는 "쓰레싱"이다.
"쓰레싱"이란, 필요한 데이터가 메인 메모리에 존재하지 않거나 다양한 이유로 인해
I/O 작업이 지나치게 빈번하게 발생하는 현상을 말한다.
이러한 상황이 지속될 경우, 가상 메모리 시스템의 성능이 저하되어,
가상 메모리를 사용하는 것이 오히려 역효과를 낳게 된다.
이를 "쓰레싱"이라 한다.
쓰레싱 문제를 해결하는 것은 가상 메모리 시스템 설계와 운영에 있어 매우 중요하다.
이 문제에 대응하기 위해 다양한 알고리즘이 개발되었다.
현재 가장 효과적인 해결 방안 중 하나는 '지역성(Locality)의 원리'를 적용하는 것이다.
지역성의 원리는 프로그램이 실행되는 동안
데이터와 명령어의 접근 패턴이 시간적 또는 공간적으로 집중되는 경향이 있다는 관찰에 기반한다.
이 원리를 이용하여, 시스템은 현재 사용되고 있거나
곧 사용될 가능성이 높은 데이터를 메인 메모리에 우선적으로 유지함으로써
I/O 작업의 빈번한 발생을 줄이고, 쓰레싱을 방지한다.💻 페이지
가상메모리 시스템에서는 보통 페이징 시스템을 사용한다.📖 페이지 테이블 엔트리
가상메모리의 페이지 테이블 엔트리에서는 몇가지 값이 추가된다.
present bit, modify bit, 그밖에 다른 제어 비트들이 추가된다.
present bit - 현재 페이지가 메인메모리에 존재하는지를 나타낸다.
modify bit - 해당 페이지가 현재 수정되었는지 아닌지를 나타낸다.
수정되었다면 수정된 내용을 디스크에 기록해야한다.📖 페이지 테이블
전장의 실제 메모리 시스템에서와 마찬가지로 페이지 번호와 offset으로 구성된 논리주소가
물리주소로 변환되며
페이지 테이블은 프로세스 크기에 따라 변경되므로 레지스터가 아닌 메모리에 저장된다.
<이유>
- 레지스터는 제한된 용량과 고정된 위치를 가지므로 가변하는 데이터를 처리하는데 적합치 않다.
- 메모리보다 크기가 작으며 특정한 목적을 위해 보통 사용되므로 유연성이 부족하다.
위 사진은 이전 페이징 시스템에서 물리 주소를 찾아내는 방법이다.
가상주소의 페이지 번호를 통해 프레임 위치를 찾아내고 offset을 더해서 물리주소를 구했다.
하지만 가상메모리 시스템에서 프로세스는 굉장히 큰 가상 메모리를 가질수 있다.
(메인 메모리에 페이지가 존재치 않더라도 가상 메모리 내의 프로세스에 대한 테이블은 모두 존재)
예를 들어 2GB짜리 프로그램이 있다고 해보자.
페이지 하나의 크기가 9바이트로 표현이 가능하다면 페이지의 개수는 2의 22승개이다.
이처럼 페이지 테이블의 크기가 굉장히 커지기에 가상메모리에서 괸라하며
여러 방법을 통해 일부만 메인 메모리에서 관리한다.📄 계층적 페이지 테이블
큰 페이지 테이블을 관리하기 위한 방법중 한가지로 계층적 구조를 사용한다.
이 구조의 핵심은 페이지 프레임 1개의 크기 만큼 페이지 테이블을 압축하는 것이다.
페이지 테이블에 대한 페이지 테이블을 만들고 그에 대한 페이지 테이블을 만들어서
결국 페이지 프레임 1개의 크기가 될때까지 페이지 테이블을 압축한다.
설명만 들어서는 잘 모르겠으니 좀더 자세히 알아보자
위 사진은 32비트 주소 체계에 적용가능한 2단계 계층적 페이지에 대한 사진이다.
1. 4K(2^12 바이트) 크기의 페이지를 사용한다면
페이지테이블은 2^20개의 PTE(page table entry) 로 구성된다.
2. PTE하나의 크기가 4바이트라고 가정한다면
페이지 테이블의 크기는 4M(2^22)이며 이는 페이지 하나에 들어가지 않는다.
3. 이 페이지 테이블은 페이지를 2^10개나 사용하기에 메모리에 적재하지 않고 가상메모리에 저장되며
페이지 테이블에 대한 또다른 테이블을 만들어 메모리에 적재한다.
4. 페이지 테이블에 대한 페이지 테이블(root 테이블)의 크기는
PTE 크기 * 개수이니 2^12바이트며 이는 4K로 하나의 페이지에 들어간다.
이런식으로 2단계 혹은 그 이상의 단계로 계층적 페이지 테이블을 사용하며
root 테이블의 크기가 페이지 하나의 크기와 동일해질때까지 사용한다.
*** 주의점
페이지 테이블의 크기는 페이지의 개수 * 페이지 테이블 엔트리의 크기로 결정된다.
위 사진은 2단계 페이징 시스템에서 주소가 변환 되는 과정을 나타낸다.
가상 주소는 루트/테이블/offset에 대한 정보로 구성되어있다.
이때 10bit/10bit/12bit로 구성되어 있는 이유는
페이지의 크기가 4K이니 12bit는 offset을 나타내며
남은 20비트 중에 root 페이지의 개수가 10개이니 10bit를 1개의 root 페이지 테이블이
2^10개의 페이지 테이블을 관리하니 10bit를 준다.
<변환 과정>
1. 첫 10비트에서 root 테이블 안에서 원하는 페이지 테이블의 위치를 알려준다.
2. 그다음 10비트는 페이지 테이블에서 원하는 페이지의 번호이며 이를 통해 Frame값을 얻는다.
3. offset을 더하여 메인 메모리 내의 물리주소를 얻어낸다.
위 과정에서 1번이던 2번이던 원하는 페이지가 메모리 상에 존재하지 않는다면
page fault가 발생한다.📄 역페이지 테이블
페이지 테이블의 문제가 프로세스가 커지면 테이블 크기도 같이 커진다는 것이였다.
이를 해결하기 위한 방법중 하나로 역페이지 테이블가 있다.
프로세스별로 페이지 테이블을 관리하는 것이 아니라
메인 메모리의 페이지 프레임을 기준으로 현재 어떤 프레임에 어떤 프로세스의 페이지가 적재되어있는지를 나타낸다.
역페이지 테이블에서의 테이블 인덱스는 프레임의 번호를 나타낸다.
테이블 엔트리에는 현재 사용중인 프로세스의 ID, 페이지의 번호 그리고 chain등의 정보가 저장된다.
역페이지 테이블에서의 문제는 원하는 페이지를 찾기위해서 모든 테이블을 돌아봐야 할수도 있다는 점이다.
이를 어느정도 완화 시키기 위해 hash 함수와 chain을 사용한다.
위와 같은 역페이지 테이블이 존재한다고 하고
hash 함수는 페이지 번호 %10 연산을 한다고 해보자.
hash 함수의 결과 값이 같은 프레임들끼리는 chain을 통해서 묶여있다.
위 사진처럼 0번 테이블 엔트리에서 chain은 3을 가리키듯이 말이다.
주소 변환 과정은 다음과 같다.
1. 가상주소에서 페이지 번호를 받는다.
2. 해시 함수를 통해 결과값이 동일한 첫번째 프레임번호를 리턴한다.
3. 원하는 페이지가 나올때까지 chain을 통해서 해시 함수의 결과값이 동일한 엔트리를 찾는다.
* 해시함수가 리턴하는 것은 원하는 프레임의 번호가 아닌 결과값이 같은 첫번째 프레임의 인덱스이다.
* 원하는 엔트리를 찾으면 직전 엔트리의 chain값을 리턴하여 프레임 번호로 사용한다.계층적 페이지 테이블이던 역페이지 테이블이던 둘다 장단점이 존재한다.
<계층적 페이지 테이블>
프로세스의 크기가 커질수록 페이지 테이블의 크기가 커진다.
<역페이지 테이블>
공간은 매우 절약되지만 페이지 접근시 계층적 페이지 테이블에 비래서 많은 시간이 소요된다.📖 TLB (Translation Lookaside Buffer)
<필요성>
가상메모리 참조에는 최소 두번의 물리 메모리 참조를 수반한다.
1. 해당 페이지 테이블 항목 참조
2. 요구된 데이터 참조
를 위해 반드시 2번의 물리 메모리를 참조해야한다.
이는 메모리 접근 시간을 2배 이상으로 늘려 성능의 저하를 야기한다.
이를 해결하기 위해 사용하는것이 TLB이다.
<TLB>
TLB는 고속 캐시이다. 캐시가 가장 최근 참조한 데이터나 명령어등을 유지하듯이
TLB도 가장 최근 사용한 페이지테이블 항목을 유지한다.
주소 변환과정은 다음과 같다.
1. 페이지 번호가 TLB에 저장되어 있는지 확인한다.
존재한다면 TLB hit라 한다.
2. TLB에 없다면 페이지 테이블을 참조한다. (TLB miss)
3. 메인 메모리 상에 페이지가 존재하지 않는다면 Page fault가 발생하며
보조 기억장치에서 페이지를 반입하여 페이지 테이블을 교체하던 갱신하던 한다.
page table을 활용할때는 page번호를 인덱스로 접근하지만
TLB에서는 인덱스로 활용이 불가하다.
대신 다수의 TLB 항복들을 동시에 조사하여 페이지 번호가 5인 항목을 찾아 프레임 번호를 리턴한다.
* TLB에 저장된 것은 값을 원하는 페이지가 들어있는 Frame의 번호를 포함하는 page table entry이다.📖 페이지 크기
페이지의 크기를 결정하는 것은 매우 중요하다.
<너무 작은 경우>
페이지 크기가 너무 작다면 페이지 테이블의 크기가 커지고 이는 가상 메모리 공간의 낭비로 이어진다.
또한, 계층적 페이지 테이블처럼 여러 페이지 테이블로 구성되기에 페이지를 찾는데
공간적, 시간적 오버헤드가 커진다.
<너무 큰 경우>
하지만 페이지 크기가 너무 크다면 또 문제가 생긴다.
페이지 크기가 커지면 페이지 폴트가 더 많이 발생하게 된다.
어차피 프로세스별로 같은 공간을 준다고 하면 페이지 개수와 페이지 폴트가 무슨 상관이냐고 할 수도 있다.
<예시>
A 프로세스가 3개의 페이지 프레임을 받았다고 해보자.
A 프로세스는 4개의 페이지로 구성되어 있다.
현재 작업 중에 1번의 중간쯤에 있는 함수, 2번과 3번의 함수 몇 개, 4번의 함수를 사용해야 한다고 하면
페이지 프레임의 개수가 3개밖에 안 되니 계속해서 페이지 폴트가 발생한다.
비록 사용하는 건 함수 몇 개이지만 쪼갤 수가 없기 때문이다.
만약에 페이지의 크기가 더 작아서 함수 하나씩 필요하다고 한다면 필요한 함수와 구간들만 넣어두고 사용하면 된다.
따라서 페이지 폴트의 횟수가 줄어들게 된다.
<결론>
페이지 크기가 너무 작으면 공간적, 시간적 오버헤드가 커진다.
또한, TLB(TLB 크기 고정 시)에 저장된 PTE(Page Table Entry)의 비율도 상대적으로 적어져서 TLB hit가 줄어든다.
하지만 페이지 크기가 너무 커진다면 페이지 폴트가 자주 발생한다.
그렇기에 너무 커서도 너무 작아서도 안 되는 적당한 크기를 잘 찾아야 한다.💻 세그먼테이션
세그먼테이션은 의미있는 단위로 메모리를 쪼갠다.
예를 들어 관련 함수끼리 나누거나, 관련된 부분끼리 나누게 된다.
이는 결국 동적 할당과 유사한 방법이며 external fragment가 발생하게된다.
이로 인해 compaction등으로 인해 시간 소요가 커진다.
하지만 장점도 존재한다.
세그먼테이션 기법은 데이터 공유와 보호에 장점을 가진다.
PCB,코드,데이터,스택으로 4개의세그먼트로 나눈다고 해보자.
이 경우 코드 영역은 공유가 가능하다.(불변하기에)
이 처럼 부분을 나눠 read-only인 세그먼트의 경우 동시 접근이 가능하게 하여 공유에 이점을 가진다.
또한 세그먼트 단위로 권한을 부여하여 보호에도 이점이 존재한다.📖 세그먼테이션 테이블
가상주소는 세그먼트 번호와 offset으로 구성되어있다.
세그먼트 테이블 엔트리에는 present 비트와 Modify비트 그밖에 다른 제어비트가 있으며
길이(세그먼트 크기)와 새그먼트 베이스(시작주소)가 존재한다.
주소 변환시 세그먼트 번호를 통해 세그먼트 테이블에서 base를 얻어내고
이 base에 offset을 더한다.
이때 더한 주소가 Length보다 크다면 오류가 발생하게 된다.📖 반전?
실제 시스템에서는 순수 세그먼테이션 기법을 사용치 않는다.
복잡한 메모리관리와 외부단편화 등의 문제로 매우 비효율적이기에 사용치 않고
페이징 시스템과 혼합하여 사용한다.💻 세그먼테이션과 페이징 결합
프로세스 이미지를 의미있는 단위(PCB,코드,데이터,스택) 으로 나누고
이 나눈부분을 페이지로 나눈다.
이렇게 사용하게 된다면 세그먼테이션과 페이징의 장점을 모두 사용가능하다.
이 경우 메모리에 적재되는건 결국 페이지 단위이며 외부단편화 문제가 없다.
또한 세그먼트 단위로 처음에 나눴기에 데이터 공유와 보호에도 이점이 있다.
📖 가상주소와 테이블 엔트리
가상주소는 총 3파트로 나뉜다.
앞서 배운 2단계 계층적 페이징처럼 사용되는데 세그먼트의 번호, 페이지의 번호, offset으로 나뉜다.
세그먼트 테이블 엔트리에는 컨트롤 비트와 길이 그리고 베이스가 존재한다.
페이지 테이블 엔트리에는 present bit, modified bit, 제어비트, 프레임 번호가 있다.
Q) 여기서 세그먼트 베이스와 length는 어떤걸 의미할까?
A) 이 시스템에서 세그먼트 하나는 결국 페이지 테이블을 의미한다.
따라서 length는 페이지 테이블의 개수와 관련이 있으며 Base는 페이지 테이블의 시작주소와 관련있다.
주소 변환은 위와 같이 이루어진다.
1. 세그먼트 번호를 통해 해당 세그먼트의 시작점을 찾는다.
2. 이 세그먼트는 사실 페이지 테이블이며 페이지 테이블에서 page번호를 통해 프레임의 시작주소를 얻어낸다.
3. offset을 더해 실제 메모리의 주소를 알아낸다.💻 정책
페이지를 사용함에 있어서 논의되어야 하는 다양한 정책들이 존재한다.
1. 반입 - 언제 메인 메모리로 적재할 것인가.
2. 배치 - 메인메모리의 어디에 적재할 것인가.
3. 교체 - 어떻게하면 page fault가 적게 교체할 것인가.
위 정책들에 대해서 알아보자.📖 반입 정책(Fetch Policy)
반입정책은 각 페이지를 가져올때 필요한 페이지만 가져올지 (요구페이징)
그렇지 않다면 관련된 다른 페이지들도 미리 가져올지의 대한 문제다. (선페이징)
페이지의 개수가 1개던 3개던 n개던 페이지를 가져오는데 걸리는 시간은 동일하기에 고민한 문제이다.
하지만 가상메모리를 사용하는 이유는 메인메모리의 공간부족 때문인데 미리 가져오는 것은
메모리 사용에 비효율적이기에 요구페이징 방법을 사용한다.📖 배치 정책(Placement Policy)
세그먼테이션과 페이징의 결합 그리고 순수 페이징 시스템에서 배치는 문제될 것이 없다.
📖 교체 정책(Replacement Policy)
가장 중요한 것은 교체 정책이다.
페이지를 하나 가져올라면 하나의 페이지를 버려야한다.
이때 버릴 페이지를 어떻게 선택할 것인가 에 대한 고민을 해야한다.
가장 이상적인 것은 버려도 괜찮은 즉, 이후 사용계획이 없거나 한참뒤에 사용하는 페이지를 버리는 것이다.
하지만 이는 불가능하다.
앞으로 어떤 프로세스의 페이지가 얼마나 사용될지를 알수 없기 때문이다.
따라서 현재까지 사용을 기반으로 예측하여 페이지를 버릴수 있도록 해야하며
이에 대한 방법은 아직도 합의 되지 않았다.
총 4가지 방법이 있다.
1. Optimal
2. LRU(Least Recently Used)
3. FIFO(First-In-First-Out)
4. 클록(Clock)
위 알고리즘의 성능은 page fault의 발생횟수로 정의된다.
각 프로세스마다 페이지 프레임을 3개씩 할당하고
페이지가 다음과 같은 순서로 들어온다고 했을때 위 4개의 방법들을 비교해보자.📄 Opimal
Optimal은 가장 오랫동안 사용치 않는 페이지를 선택하여 버리는 방식을 취한다.
위 순서에서 처음 page fault가 발생하는 시점은 5번 페이지가 들어올때 이다.
이때 뒤 순서를 참고하여 현재 프레임에 존재하는 페이지 중 가장 나중에 사용할 페이지는
1번 페이지니 1번 페이지를 버린다.
위와 같은 방식으로 진행하여 총 3번의 page fault가 발생한다.
하지만 사실 이 방법은 구현이 불가하다.
Optimal 방식은 기준점으로 실제 구현가능한 방법들은 Optimal보다 page fault가 적게 발생할수 없다.📄 LRU
LRU 방식은 참조 지역성의 원리에 기반한다.
가장 최근에 사용된 것은 그 다음에 또 사용될 가능성이 높다.
따라서 가장 최근에 사용된 페이지는 남겨두고 최근에 사용되지 않은 페이지를 버린다.
위 순서에서 page fault 가 처음 발생하는 경우는 5번 페이지를 사용할때 이다.
이때 앞에서 살펴보니 가장 오랫동안 사용하지 않은 페이지는 3번페이지이다.
따라서 3번페이지를 버리고 5번으로 교체한다.
위와 같은 방법으로 진행하면 page fault는 총 4회 발생하게 된다.
<장점>
LRU 방식은 구현가능한 방식들 중 가장 Optimal의 성능에 근접한다.
<단점>
하지만 단점도 존재한다.
LRU에서는 각 페이지마다 실행된 시간을 저장해야 한다.
그렇기에 시간을 저장할 비트를 따로 빼야하며 시간들 또한 저장해야한다.
최소 페이지 하나당 4byte가 필요하며 페이지의 개수가 많아 질수록 공간적 오버헤드가 크게 발생한다.
또한 제일 오래 사용하지 않은 페이지를 찾아야하기에
모든 페이지를 비교후 제일 오랫동안 사용하지 않은 페이지를 찾아야한다.
그래서 시간적 오버헤드가 발생한다.📄 FIFO
FIFO는 말 그대로 처음 들어온 페이지가 나간다.
순환 버퍼처럼 페이지 프레임을 다루어서 라운드 로빈 스타일로 페이지를 제거한다.
가장 오래있던 페이지를 가르키는 포인터 하나만 있으면 되기에
시간적,공간적 오버헤드가 거의 발생하지 않는 방법이다.
하지만 page fault가 가장 많이 발생하며 실제로는 사용치 않는 방법이다.
*** FIFO Anomaly
페이지를 더 많이 준다면 당연히 page fault의 횟수도 줄어든다.
하지만 FIFO에서는 오히려 page fault가 증가하는 상황이 발생하기도 하는데
이를 FIFO Anomaly라 한다.
<페이지가 3개일때>
참조 문자열: 1 2 3 4 1 2 5 1 2 3 4 5
프레임 상태:
1: [1] [1,2] [1,2,3] [2,3,4] [2,3,4] [2,3,4] [3,4,5] [4,5,1] [4,5,1] [5,1,2] [1,2,3] [2,3,4] [3,4,5]
페이지 폴트: 9회
<페이지가 4개일때>
참조 문자열: 1 2 3 4 1 2 5 1 2 3 4 5
프레임 상태:
1: [1] [1,2] [1,2,3] [1,2,3,4] [1,2,3,4] [1,2,3,4] [1,2,3,5]
[2,3,5,1] [3,5,1,2] [5,1,2,3] [1,2,3,4] [2,3,4,5]
페이지 폴트: 10회
이처럼 오히려 page fault의 횟수가 증가하는 상황이 발생하기도 한다.📄 Clock
LRU와 FIFO의 중간쯤 되는 기법이다.
페이지 하나당 use bit를 한개 만 사용하여 공간적인 오버헤드를 줄였다.
use bit는 특정 기간내에 사용된 페이지를 표시하는데 사용된다.
처음 교체가 된 페이지의 경우 금방 사용될것이기에 바로 1로 표시한다.
프레임들이 환형 구조로 되어있다고 가정하고 사용하는데
처음 페이지가 들여오면 모두 1로 설정이 된다.
페이지를 교체할때는 use bit가 0인 페이지를 교체하게 된다.
처음에는 모두 1이였던 비트들을 프레임 포인터가 지나가면서 0으로 만들고 넘어간다.
한바퀴를 돌았는데도 해당 페이지가 아직 0을 가르킨다면
해당 기간동안 페이지가 사용되지 않은것이기에 해당 위치에서 대기하다가 교체가 필요하면 해당 페이지를 내보낸다.
*** 중요한점
포인터는 항상 빙빙 도는것이 아니다.
교체할 페이지가 필요할때만 돌면서 1인 비트를 0으로 만들고
0인 비트를 만나면 교체를 하게된다.
위 사진을 보고 좀더 자세히 설명해보자.
처음 들여온 페이지들은 모두 1로 표시되어있다.
1. 5번 페이지를 들여와야 하는데 현재 모든 비트가 1이니 포인터는 한바퀴를 돌면서 모두 0으로 만든다.
2. 한바퀴를 다돌고 다시 2번 페이지에 도착했을때 아직도 use bit가 0이니 들어있는 페이지를 교체한다.
3. 교체후 포인터는 그 다음 페이지(3번)로 넘어간다.
4. 또 교체를 원한다면 현재 3번페이지의 use bit가 0이니 3번 페이지를 교체해준다.
위 과정을 반복한다.
이때 중요한것은 바늘이 한바퀴 돌기전에 use bit가 0인 페이지가 다시 사용된다면
use bit는 1로 바뀌며 포인터는 이전에 가르키던 위치에 그대로 존재한다.
📄 결론
각 방법은 다음과 같은 그래프를 그린다.
x축은 할당된 프레임의 수를 y축은 page fault의 수를 나타낸다.
프레임의 수가 늘어날수록 페이지 폴트가 적게 발생함을 알수있다.
또한 Clock은 LRU와 FIFO의 중간수준의 성능을 보임을 알수있다.
대다수의 OS들은 LRU와 Clock 기법중 하나를 선택하여 사용한다.💻 적재집합 관리
대다수의 OS들은 LRU와 Clock 기법중 하나를 사용한다.
이때 고려해야할 사안이 2가지 존재한다.
1. 프로세스 실행중 할당된 페이지 프레임의 개수를 고정시킬 것인가?
1) fixed-allocation : 페이지 개수 고정
2) variable-allocation : 상황따라 다르게, 이게 사실 훨씬좋다.
2. 페이지 교체시 내 페이지만 교체할 것인가?
1) local-scope : 내꺼만 교체
2) global-scope : 남의 것도 가능
위 4가지를 조합하여 총 3가지 방식이 나온다.
1. fixed-alloaction & local-scope
2. variable-allocation & loacl-scope
3. variable-allocation & global-scope
fixed와 global은 애초에 불가능하다.📖 working-set
3가지를 자세히 알아보기전에 working-set 이론을 알아보자
위 그래프는 프로그램이 실행되면서 시간이 지남에 따라 "필요한 페이지의 수"의 변화를 나타낸 그래프다.
* resident-set은 그래프에는 없지만 내가 지금 사용중인 페이지를 나타낸다.
그래프를 잘 살펴보면 확 증가했다가 횡보했다가 확 증가했다가 횡보한다.
감소할때도 확 감소하다가 횡보했다가를 반복한다.
필요로 하는 페이지의 수가 변화할때만 요동치고
원하는 만큼 페이지가 들어온다면 안정기에 접어든다.
즉, 원하는 페이지의 수가 계속해서 변하며 이때문에 variable-allocation이 더 효율적임을 알수있다.📖 조합
1. fixed-alloaction & local-scope
처음 시작시에 프로그램 특성 파악 + 이전 실행시 working 파악후 페이지 프레임을 고정시켜준다.
너무 많이주면 낭비가 너무 적게주면 page fault가 계속 발생할 것이다.
2. variable-allocation & loacl-scope
페이지의 개수는 변하지만 내꺼에서만 페이지를 교체하는 방식이다.
variable-allocation을 할건데 3번 방식처럼
자동적으로 하는것이 아닌 처음에 할당 시켜주고 검사를한다.
page-fault가 많이 발생한다면 페이지를 더 많이주고 남는다면 줄인다.
이렇게 주기적인 검사를 통해서 page의 개수를 조절한다.
위 방식에서 가장 적합한 교체 방식은 "LRU"방식이다.
LRU 방식의 가장 큰 문제는 모든 페이지의 실행된 시간을 알아야 한다는 것이다.
하지만 local-scope사용시에 페이지 몇개의 실행된 시간을 알고 있으면 되고
더 줄인다면 시간이 아닌 어차피 할당된 프레임의 개수를 알고있으니
실행된 순서만 적어주면 된다. 따라서 공간적 오버헤드 또한 줄어든다.
3. variable-allocation & global-scope
위 방식을 풀어서 설명해보자.
나의 페이지 개수도 계속해서 변하고 남의 페이지를 가져올수 있다.
이때 남의 페이지는 타 프로세스가 사용하지 않는 페이지를 가져올 것이다.
즉, 이는 working-set이 줄어드는 프로세스의 페이지를 하나 가져온다는 것을 의미한다.
이 방식이 working-set 이론을 반영하는 가장 간단한 방법이다.
위 방식에서 가장 적합한 교체 방식은 "Clock" 방식이다.💻 UNIX
UNIX 시스템의 가상메모리에 대해서 알아보자.
user-process : 페이지 기반 가상메모리사용
kernal-process : 동적할당을 하며 변형된 buddy system을 사용한다.
page 교체는 변형된 clock 기법을 사용한다.
📖 two-handed clock
UNIX에서 사용하는 변형 clock 기법이다.
전통적인 Clock 기법의 문제점은 바늘이 한개라는 것이다.
바늘은 페이지를 교체할때만 움직이며 우리는 page fault가 발생하는 시점을 알수없다.
따라서 굉장히 오랫동안 page fault가 발생하지 않고 바늘이 대기해야하는 상황이 발생한다.
이때 page를 교체하려면 모든 비트가 1이기에 전체를 검사해야한다.
이런 방식은 LRU처럼 모든 페이지를 검사해야하기에 비효율적이다.
이를 막기위해 UNIX에서는 바늘을 2개쓴다.
fronthand 바늘 : 속도 조절이 가능하며 주기적으로 움직이면서 referrence bit를 0으로 만드는 작업을 한다.
적절한 속도를 유지하는 것이 중요하다.
backhand 바늘 : backhand바늘이 지나가며 referrence bit가 0인 페이지를 모아서 교체할 페이지의 리스트를 만들어둔다.
이렇게 미리 리스트를 모아둘 경우의 장점은 다음과 같은데
<장점1>
Clock의 경우 프레임당 1비트씩만 사용하기에 공간적인 오버헤드가 최소이다.
문제는 시간적인 부분이였는데 UNIX에서의 방법은 미리 교체할 페이지들을 모아뒀기에
바로 교체할 페이지를 찾을수가 있다.
따라서 공간적인 오버헤드와 시간적인 오버헤드 모두가 최소치가 되기에 매우 효율적이다.
<장점2>
또다른 장점은 Modified-bit가 1인 페이지들은 결국 디스크에 수정된 내용을 반영해 줘야한다.
몇개의 페이지를 디스크에 쓰던 시간은 비슷한데
위방식으로 진행시 미리 페이지들을 모아두고 한꺼번에
modified bit가 1인 놈들을 디스크에 한꺼번에 쓸수있기에 매우 효율적이다.
<장점3>
바늘 간의 간격(시간)을 조절가능하다.
paged-out 리스트의 개수를 보고 바늘의 속도를 조절하여 성능을 조절가능하다.💻 Windows
page 기반 allocation 사용한다.
variable-allocation & local scope를 사용한다.
-> LRU를 사용하기 위함
working-set 기반 메모리 관리이다.
처음 적절한 크기의 페이지 프레임 할당후 지속적으로 관찰하여
페이지의 개수를 조절해줘 working-set을 맞춰준다.
학생