프로세스를 사용하기 위해선 메모리에 올려야 한다.
그럼 언제 메모리에 가져다 놓는가?
- Demand fetch(필요로 할 때 가져온다)
- Anticipatory fetch(예상해서 가져온다)
메모리 빈 공간중 어디에 가져다 놓는가?
- First-fit(첫 번째로 빈공간), Best-fit(필요한 공간과 크기가 비슷한 공간), Worst-fit(best의 반대, 가변 파티션이 가능한 조건에서)
교체가 발생할 때 무엇을 교체할 것인가?
- 교체전략을 말한다. 디스크에서 데이터를 갖고 왔는데 메모리에 빈자리가 없을 경우 메모리를 점유하고 있는 것 중에서 누군가를 교체시켜야 한다. 이게 바로 replacement 문제이다. 메모리에서 쫓겨날것은 앞으로 잘 사용되지 않을 프로그램이 쫓겨나야 한다.
페이지 교체 예제
1. 페이지 A를 첫 번째 메모리에올린다. Fault가 발생하는데, 메모리에 처음 올리는 경우 발생한다.
2. 페이지 B를 두 번쨰 메모리에 올린다. 마찬가지이다.
3. 페이지 C를 메모리에 올린다. 마찬가지이다..
이 후 D를 디스크에서 메인메모리로 가지고 오려고 봤더니 공간이 없다.
하나를 쫓아내고 D를 적재해야한다. Replacemt가 발생했다.
수정된 페이지라는 것은 적재된 후 데이터가 변경된 것이다. 이러면 디스크와 메모리의 정보가 다르기 때문에 디스크에 있는 데이터를 메모리의 값으로 수정해주어야 하므로 시간이 보다 오래 걸린다.
또한 자주 사용되는 페이지를 선택하게 되면 곤란해진다,, 자주 사용되는 페이지는 교체 페이지로 선택하지 말아야한다, 이런 것 들을 감안하고 교체페이지를 선택해야한다.
페이지 선택시 유의해야 하는점
교체페이지 선택:
- 어느 페이지를 제거할 것인가.. 새로 반입되는 페이지를 위한 공간 확보가 필요하다
수정된는 페이지는 저장되어야 한다:
- 저장에는 보다 많은 시간이 소요된다.
자주 사용되는 페이지를 교체페이지로 선택하지 않아야 한다:
자주 사용되는 페이지는 다시 반입되어야할 페이지이다.
Page Replacement Algorithm
Optimal Replacement
최적의 교체 전략이다 이게 가능하려면 미래를 알아야 하기 때문에 현실세계에선 불가능하다.
하지만 존재하는 이유는 성능 비교를 위해서이다.
페이지 교체 순서
A - B - C - D - C- A - A - D - C - B
만약 4번째 D가 참조되었을 때 누구를 교체해야 할까
최선의 선택:
가장 먼 미래에 참조될 것을 선택 = B
최악의 선택:
가장 가까운 미래에 참조되는것을 선택 = C
현실 세계에서 이 알고리즘은 실현 불가능하지만 타 알고리즘 들의 성능을 비교하기 위해 활용된다.
NRU(Not Recently Used)
페이지들을 4가지의 속성으로 분류한다.
페이지에는 Refresence bit와 Modified bit이 존재한다 이를 이용하여 4가지로 분류한다.
Class1 = 참조되지도, 수정되지도 않은 클래스
Class2 = 참조는 되지 않았지만, 수정은 된 클래스
Class3 = 참조는 되었지만, 수정은 되지 않은 클래스
Class4 = 참조는 되었고, 수정도 된 클래스
가장 높은 우선순위로 쫓겨나는 클래스 = Class1
가장 낮은 우선순위로 쫓겨나는 클래스 = Class4
여기서 Class2는 참조는 안되었지만 수정은 되었다. 생각해보면 파일이 수정되려면 참조가 되었다는 뜻이기도 하다.
하지만 recefrence bit은 참조가 될경우 1이 되지만 주기적으로 0으로 clear을 시킨다. 아주 오래전에 참조가 되었어도 1이면 문제가 되기 때문이다.
Class2와 Class3은 별 차이가 없다고 생각할 수 있지만, 빈번하게 사용되는 페이지보다 수정되고 사용되지 않는 페이지를 제거하는게 낫다는 이유다.
FIFO(First In First Out)
가장 오래전에 반입된 페이지를 교체하는 전략이다.
페이지들을 리스트로 연결한다.
리스트 헤드에는 오래된 페이지가, 꼬리에는 새로 들어온 페이지가 위치하게된다.
단점: 메모리에서 가장 오래된 페이지가 자주 사용되는 페이지일 수 있다는 것이다.
Second Chance Page Replacement Algorithm
FiFO전략을 조금 바꾼 알고리즘이다.
그림 (a)에서 가장 오래된 페이지는 A이다. 하지만 교체전략에 대입 후 새로 들어온 페이지처럼 리스트의 마지막으로 갔다.
오래되고 사용안된(R = 0) 페이지를 선택하는 전략이다.
만약 오래되었지만 최근에 사용되었다면(R = 1) 두번째 기회(second chance)를 부여한다.
즉 R = 0으로 수정하고 리스트의 마지막에 삽입한다.
R = 0으로 수정하고 새로 반입된 것 처럼 처리한다.
The Clock Page Replacement Algorithm
Second Chance와 FIFO는 연결 리스트를 사용하므로 노드를 제거/삽입하는 시간이 추가된다.
이런 단점을 보완하기 위하여 나온 알고리즘이다.
포인터가 가르키는 페이지가 살펴볼 페이지가 된다.
reference bit을 봐서 0이면 쫓겨나고 1이면 0으로 만들고 포인터를 시계방향으로 움직인다.
LRU(Least Recently Used)
최근에 사용된 페이지는 조만간 다시 사용될 것이라는 가정에 기초한다.
하드웨어 방식으로 가장 오래전에 사용된 페이지를 선택한다.
가장 오래전에 사용된 페이지를 쫓겨날 대상 1순위로 설정하는게 Best이다.
페이지들을 연결 리스트로 구성해서 사용한다.
- front: 가장 최근에 사용된 페이지
- rear: 가장 안 사용된 페이지
리스트를 매 메모리 참조 마다 업데이트 해야한다. 하지만 구현은 가능하나 성능은 매우 안좋아진다.
하드웨어 방식을 사용한다.
HW counter( = C)를 이용하여 page table을 유지한다.
- 매 명령마다 자동으로 C값을 증가시킨다.
- 각 메모리 참조시 현재 C값은 page table의 해당 페이지 정보에 저장된다.
- page fault시에 OS는 가장 C값이 작은 ㅍ에ㅣ지를 선택한다
- 주기적으로 C값을 0으로 초기화 한다.
2. n * n bit의 행렬 사용 방식
(a): 0번 페이지가 참조되었다. 0번 열을 따라 1로 만들고 행을 따라 0으로 만든다.
(b): 1번 페이지가 참조 되었다. 1번 열을 따라 1로 만들고 행을 따라 0으로 만든다.
이렇게 나아가다 보면 최근에 사용된 페이지의 열에는 1이 많을 것이고 가장 사용이 안된 페이지의 열에는 0이 많을 것이다.
e가 끝이라고 가정 할 경우 행에 0이 가장 많은 0번 페이지가 쫓겨나게 된다.
NFU(Not Frequently Used)
각 페이지별로 소프트웨어적인 카운터를 유지한다
매 클록 인터럽트마다 OS는 0 또는 1(당시 refrence bit)을 카운터에 더한다.
page fault시에 카운터 값이 가장 적은 페이지가 교체된다.
단점: 어떤 페이지가 집중적으로 과거에 참조되었었는데 극단적으로 count가 높아졌다면 영원히 삭제되지 않을 수 있다.
지역성의 원리
참조 지역성
짧은 기간동안 동일한 메모리 장소들을 프로세서가 반복적으로 접근하는 경향
시간지역성(Temporal Locality)
- 어떤 메모리 장소가 참조되었으면 조만간 같은 장소가 다시 참조되는 경향
공간지역성(Spatial Locality)
- 어떤 메모리 장소가 참조되었을 때 조만간 그 근방의 장소가 참조되는 경향
모든 데이터가 균등한 빈도로 엑세스 된다고 하면 모든 데이터를 담을만한 메모리에 담으면된다.(레지스터, 캐시메모리, ram, 하드디스크의 차이를 두지않고)
가상 메모리에서 메인 메모리와 디스크 사이에 배치를 할 때 자주 사용되는것은 메인 메모리에, 덜 사용되는것은 디스크에 배치한다
지역성의 필요성이다.
void main()
{
int s1, s2, a[100], i;
s1 = 0;
s2 = 1;
for i(i = 0; i < 100; i++){
s1 = s1 + a[i]
}
}
해당 반복문 에서 배열 a의 첫 주소를 중심으로 바로 옆 공간의 데이터들에 접근하게된다. = 공간 지역성
s1은 항상 같은 공간에 대하여 비슷한 시간내에 여러번 접근하게된다. = 시간 지역성
Working set
작업집합: 프로세스가 자주 참조하는 페이지들의 집합
Thrashing
가용 메모리 공간이 너무 적어서 전체 작업 집합을 모두 유지할 수 없으면 프로세스는 많은 페이지 폴트를 야기하고, 결국 실행 시간이 크게 증가하는 현상
적재된 메모리의 수가 많아질수록 cpu이용률은 증가한다.
하지만 프로세스를 메모리의 용량을 초과할 정도로 계속 적재하다보면 어느순간 성능이 저하되는 순간이 온다. = Thrashing 발생
총 메모리 800kb, 1page = 4kb, 1개 프로세스 = 80kb일 경우
10개적재 -> 1개당 80kb -> 1개당 20page다. 프로세스들이 1개당 20page로 충분할 경우 trashing은 발생하지 않는다
20개적재 -> 1개당 40kb -> 1개당 10page다. 만약 10page로 불가능 할 경우 프로세스를 실행할 때 마다. fault가 발생하고 계속 메모리와 디스크 사이에 프로세스들을 replacement해야한다. -> trashing
Working Set Page Replacemenet
A, B, C는 페이지 참조가 일어나느 시점이다,
t = 500이란 500내에 참조된 page는 작업 집합이다.
마지막 page fault가 일어난 시점에서 보면 500내에 B, C가 참조되었으므로 Working set = B, C
교체 대상은 A가 된다.
CVT(Current Virtual Time): CPU의 time을 이용한 가상 시간이다.
TlU(Time of Last Use): 마지막에 참조된 시간을 나타낸다.
Periodic clock tick: 주기적인 CPU 인터럽트로 발생할 때 마다 R비트가 0이된다.
매 page fault에서 R = 1인 페이지는 CVT값을 TLU에 기록한다.
마지막 Page fault를 기준으로 페이지 테이블을 작성해본다.
| R | TLU | |
| A | 0 | 1824 |
| B | 0 | 2024 |
| C | 1 | 2324 |
A, B, C는 모두 Page fault전에 참조되었지만 TLU를 기록하는 때는 page fault에서 이다.
A의 R비트는 첫 tick에서 0이 되었다. 참조는 이전이지만 page fault는 1824이므로 1824가 된다.
B의 R비트는 두번쨰 tick에서 0이 되었다. 참조는 이전이지만 page fault는 2024이므로 2024가 된다.
C는 참조 이후 tick이 발생하지 않았으므로 R은 1이된다. page fault인 2324가 된다.
최종 Working Set Page Replacement
마지막 Page fault를 기준/ t = 500
| R | TLU | age=(CVT - TLU) | |
| A | 0 | 2004 | 320 |
| B | 0 | 2024 | 300 |
| C | 1 | 2324 | 0 |
| D | 0 | 2004 | 320 |
A와 D의 page fault는 2004이다
A와 D의 R비트는 첫 번째 빨간 CPU 인터럽트 tick에서 0으로 clear되었다
B의 page fault는 2024이다.
B의 R비트는 두 번째 빨간 CPU 인터럽트 tick에서 0으로 clear되었다
C의 page fault는 2324이다.
C는 참조이후 CPU 인터럽트 tick이 발생하지 않았으므로 1이다
age는 작업집합 기간보다 나이가 큰지 확인시에 사용한다.
3번째 Page fault의 CVT는 2324이다. 2324를 기준으로 확인해본다.
A age = 2324 - 2004 = 320
D age = 2324 - 2004 = 320
B age = 2324 - 2024 = 300
C age = 2324 - 2324 = 0
t = 500 > age이므로 모두 작업 집합이다(Working set)
하지만 작업집합이라 할 지라도 메모리의 공간이 부족하다면 age가 많은 작업집합중 하나가 교체대상이 될 수 있다.