페이지 교체 알고리즘

페이지 부재와 프레임수

y축은 프레임 부제의 횟수

x는 페이지 부제의 수

 

프레임수를 많이 하면 좋은대 비효율적 입니다.

 

적은 갯수의 프레임으로 효율을 좋게할 수 있습니다.

 

 

페이지 교체 알고리즘 종류

최적 OPT - 현실적으로 구현 불가능합니다.

 

최근 최소사용(LRU) - 가장 현실적인것 하지만 비용이 많이 듭니다.

 

LRU근사 - LRU를 진화시킨 것입니다.

 

 

페이지 교체 알고리즘 종류 - 선입 선출 교체 알고리즘

가장 오래된 페이지부터 교체합니다.

 

1번이 가장 오래있었으니 내쫒을 때 1번을 가장먼저 내쫒습니다.

그 다음 2번일 것 입니다.

 

?에는 가장 오래 차지한것을 찾으면 됩니다.

2 5 3 이 있을 것입니다.

 

다음에는 2가 가장오래되었기 때문에 2가 나갈 것입니다.

 

 

선입선출 알고리즘을 어떻게 구현하는지 보여주고 있습니다.

 

그러려면 큐가 필요합니다.

왼쪽으로 들어오고 오른쪽으로 나갑니다.

 

 

스왑 아웃 할때는 invalid로 바꾸고

스왑 인할 때는 valid로 바꿉니다.

 

 

9번이 들어갔습니다.

부재비율은 총 12번에서 9번이 부재입니다.

521입니다.

 

 

1. 10

부재 비율은 10/12 입니다.

 

2. 1 5 3 2

 

프레임 부재 횟수가 더 큽니다.

 

프레임이 클수록 부재횟수가 더 큽니다.

그게 벨래디 변이라고 합니다.

(프레임 수를 늘려도 페이지 부재 수가 증가하는 현상)

 

그게 FIFO 교체 알고리즘의 문제 입니다.

 

 

페이지 교체 알고리즘 종류 - 최적 페이지 교체 알고리즘

미래를 알아야 교체를 합니다 이런 일은 일어나지 않습니다.

 

1,2,3 중에 누구를 내쫒을 까 고민할 때 앞으로 가장 오랫동안 사용하지 않을 페이지를 내보내야 합니다.

미래를 봤을 때 3이 가장 적게 사용되니 3을 내쫒 습니다.

 

첫 번째? 에는 6, 2, 3 가 들어갈 것입니다.

두 번째? 에는 6, 1, 3 이 들어갈 것입니다.

 

페이지 교체 알고리즘 종류 - 최근 최소 사용 교체 알고리즘의 개념

미래를 모르기 때문에 최적 페이지를 알 수 없지만 찾아보는 것 입니다.

 

1,2,3번 중에 하나 내쫒고 5번이 들어와야 합니다. 그 때 누가 나갈 것인가?

1번이 가장 최근에 엑세스 되고 2번이 그다음 3번이 다음이니 3번을 내쫒습니다.

 

 

1,2,6 중에 내쫒아야 하는대 가장 오랫동안 엑세스 하지 않은 것이 1번이니 1번을 내쫏 습니다.

첫 번째? 에는 5, 3, 6이 들어갑니다.

두 번째? 에는 1, 3, 6이 들어갑니다.

 

왜 가장 좋은 알고리즘인가요?

최근에 액세스한 것은 곧 다시 액세스할 가능성 크기 때문입니다.

그것을 지역성 이라고 합니다.

 

 

최근 최소 사용 교체 알고리즘 - Counter를 이용한 순서 결정 방법

페이지 참조가 한번 일어나면 논리 클록이 1식 증가합니다.

 

페이지 테이블의 예시입니다.

 

1번 페이지는 0번 프레임에 들어있습니다. 그리고 카운터는5 입니다.

2번 페이지는 1번 프레임에 들어있습니다. 그리고 카운터는4 입니다.

3번 페이지는 2번 프레임에 들어있습니다. 그리고 카운터는3 입니다.

 

카운터는 곧 클록이 몇일 때 엑세스 했는지를 알려줍니다.

 

카운터를 보고 숫자가 가장 작은 것을 지워버립니다.

 

5를 엑세스 하면 페이지 테이블이 바뀝니다.

5번 페이지가 2번 프레임에 들어감녀서 카운터는 6이 됩니다.

 

점점 가면서 카운터를 바꿉니다.

 

만약 6번을 엑세스 하려할 때 가장 오랫동안 사용하지 않은 페이지는 

카운터가 가장 작은 페이지 5가 나가야 합니다.

 

문제) 논리 클럭 9 바로 다음 순간 페이지 테이블을 적어봅시다.

 

 

문제) 논리 클럭 20 바로 다음 순간 페이지 테이블을 적어봅시다.

 

 

 

최근 최소 사용 교체 알고리즘 - 스택 를 이용한 순서 결정 방법

메모리 참조 마다 페이지 번호를 스텍에 push 합니다.

 

top에는 가장 최근에 사용한 페이지가 들어있을 것입니다.

밑바닥에는 가장 오래전에 사용한 페이지가 있을 것입니다.

 

 

이미 페이지 번호가 스텍에 있을 경우 빼서 push? 스택 안에는 현재 페이지가 있어야 합니다.

 

사실 스택은 아니고 더블 링크드 리스트가 맞습니다.

 

링크스 리스트로 구현하면 중간 항목을 뺄 때 포인터 적어도 4개 바꿔야 하고 push 할 때도 끝 부분에 포인터를 2개 갱신해야 합니다.

 

스택에 4,7,0 있다면 7을 빼서 다시 push 합니다.

 

0이 다시 나오면 0을 빼서 다시 push 합니다.

7이 다시 나오면 7을 빼서 다시 push 합니다.

 

a,b를 보면

7을 엑세스 하면 7을 빼서 맨 위에 올려둡니다.

 

이걸 왜 유지하려면 맨 밑바닥에 있는 것을 버리려고 합니다.

 

첫 번째 ?에는 1,2,6

두 번째 ?에는 1,3,6

 

맨 밑바닥을 빼서 새로 엑세스 할 것을 push 합니다.

 

페이지에 있는 것과 스택이 있는 것은 다릅니다.

스택에서 희생될 것만 찾는 것입니다.

 

교체는 프레임이 바뀌지 않습니다.