[운영체제] 3. 메모리 관리(4/5)

3.4 페이지 교체 알고리즘

주소 변환 중 page table entry까지 갔어. 거기서 valid비트가 있다고 했는데, 페이지 테이블 엔트리에 적힌 페이지 테이블 번호가 없을 경우. 혹은 있는데 absent 비트가 세팅되어 있거나. -> 페이지 프레임의 실제 데이터가 존재하지 않느다는 것.

번호가 없다는건 주소 변환이 일어나지 않은거고, 밸리드 비트가 꺼져있는 경우는 있지만 present bit가 꺼져있는건.

하드웨어는 주소변환을 하고 코드나 데이터를 cpu로부터 가져와서 실행하는데(cpu는 주소변환 불가),알아서 처리해줘 하고 page fault

-> 운영체제 코드(페이지 폴트 핸들러가 실행)

 

따라서 페이지 테이블 엔트리에 페이지 프레임 번호가 없을 수 있다 : none mapped page.

주소가 무효한지 유효한지  cpu는 모른다. -> 운영체제가 판단.

invalid한 address를 참조 -> 운영체제가 프로세스에 시그널(mode switch가 발생하는 시점에) -> 프로세스 종료.

페이지프레임이 존재한다면 -> free page frame이 없다면 다른 프로세스나 일부를 쫓아내고 필요한 페이지를 읽어야함(replace)

 

가상 메모리 기법을 살펴보는데, 페이징 성능 계산.

페이지 폴트를 낮게 유지해야 성능을 잘 유리하게 사용하는 것.

 

 

 

 

3.4 페이지 교체 알고리즘

필요한 페이지들을 페이지 프레임으로 읽어들일 땐 미스가 날 수 밖에 없음.

최초의 미스를 cold miss라고 하는데, 이게 날 수 밖에 없고 어쩔 수 없이 fault할 수 밖에 없음.

그러나 이를 최소한으로 줄여야겠지?

 

1. Optimal page replacement 알고리즘 : 향후에 참조되지 않을 페이지가 없으면 가장 먼 미래에 참조될 페이지를 교체

-> 불가능. 타 알고리즘 평가용.

 

2.Not Recently Used p r : 최근에 사용하지 않은 페이지를 교체. 엔트리에서, reperence bit는 참조 여부를,  modified bit는 변경 여부를.

NRU는 페이지를 4개의 클래스로 나눔. 레퍼런스 비트와 모디파이드 비트 세팅 유무로.

 

– Class0:NotReferenced,NotModified : 참조되지 않고 변경되지 않으면 그냥 제거하면 됨

– Class1:NotReferenced,Modified : 페이지 프레임에 기록된 데이터가 변경되었으면 교체 -> 변경된 데이터를 디스크에 적어야 하고, 그 시간 필요

– Class2:Referenced,NotModified

– Class3:Referenced,Modified

-> 고려 사항이 너무 많음.

 

3. FIFO : 는 페이지 프레임이 메모리 읽어들어오는 순서대로 교체 -> 단점 : 또 사용될 페이지들도 교체될 수 있음

 

4. Second-chance : FIFO에서, 한번 참조된 페이지는 기회를 한번 더 주겠다! : 3보다 성능좋아짐ㅋ

만약 a의 참조비트가 1이라면 제일 뒤로 보내고, 비트를 0으로 바꿈 -> 기회 1회 제공

 

5. Clock page p r : NRU보면 연결리스트 4개나 만들거야? 너무 복잡해 -> 시계처럼 배치하자

클록핸드 : 검색. fault가 나면 특정 시작 위치를 가리키고 있을 것. 해당 페이지의 레퍼런스 비트 검사 -> 0이면 쫓아내고 새로운 페이지 적재.

1이면 0으로 바꾸고 다음 엔트리 검사. 전부 1이었으면 한바퀴 돌게 됨.

NRU의 실제 구현.

 

6. LRU(Least Recently Used) : 이론적으로 탄탄, 많이 사용 but 하드웨어에서 구현 불가

스택을 유지하는데, 모든 페이지를 리스트로 연결해야하며, 메모리 참조시 마다 갱신해야함.

리스트의 탑은 가장 최근에 참조된 페이지, 바텀은 가장 오래전에 참조된 페이지.

시간이 0부터 t까지, 리퀘스트가 참조 페이지 번호니까 이 순서대로 참조가 됐음. 페이지 프레임이 4개인 경우 lru가 어떻게 동작하느냐.

이런 참조의 연속을 레퍼런스 스트림이라고 해.

 

-> 로컬리티(시간 지역성)가 강한  lru알고리즘에서는 잘 동작. 이를 하드웨어로 구현하려면 어떻게 할까?

행렬로 표시. 참조순이 0번이면 행을 전부다 1로, 그리고 열을 0으로 세팅.

두번째는 1번 이니까행을 전부 1로, 여릉ㄹ 0으로. 이러면 각 행들 중 가장 큰 게 가장 최근에 참조된 것.

물론 레퍼런스 비트가 너무 어마어마 해져서 이렇게 사용할 순 없음.

 

NFU는 지금까지는 시간과 참조비트로 결정했다면, 얘는 해시 테이블 엔트리에 참조 됐는지 안됐는지로 교체 여부를 결정.

몇 번 참조되었느냐를 중요시 해보자 한게 NFU.

 

특정 페이지의 참조 카운트를 유지. 주기적으로 페이지 폴트가 났거나 스케쥴링을 해야 되거나 하는 상황에서 엔트리에 기록된 내용을 보고 카운트를 업데이트.

-> 0~5까지 페이지가 있으면, 각 페이지마다 참조카운트가 존재. 특정 클록킹 마다 이 조 비트를 보고 카운트를 업데이트

오리지널 NFU는 처음에 0, 첫번째 주기에서 R비트를 보고 1이면 그 페이지에 +1, 0이면 통과. 시간이 지날수록 각 페이지의 참조카운트가 기록.

-> 참조 카운트가 제일 작은(덜 참조된 것을) 것을 교체. 그러나 aging이 되지 않음 : 과거에 참조가 많이 되고 지금은 안되더라도 캐시 폴루션이 일어나서 필요없는 페이지 프레임이 유지 -> 이 카운트를 줄여주는게 에이징 알고리즘.

 

이미지를 보면 a시점에 레퍼런스 비트를 페이지의 맨 앞의 비트로 하나씩 입력. 그리고 쉬프트하고 입력하고 반복.

-> 레퍼런스 카운트가 가장 작은, 가장 덜 참조된 것을 교체. 가장 최근에 참조된건 카운트 값이 가장 큰 것(2진수로 생각)

-> 동일한 주기에 같은 값이 있더라도 그 이전주기에 어떤 것이 먼저 참조되었는지 알 수 있음 -> 참조 시간 교체시에도 사용 가능

BUT 주기적으로 운영체제 코드가 동작하며 참조 카운트를 업데이트 해야하는 비용 발생.

 

 

비교해보자면,

옵티멀 -> 가장 먼 미래에 참조될 페이지 교체 : 최초의 참조 미스(cold page miss)는 무시 -> 3번의 폴트

LRU -> 4번, FIFO -> 6번, Clock -> 5번.

성능 가장 좋은게 옵티멀 -> 캐시 교체 정책 성능의 상한.

알고리즘 주고 표 그리고 시뮬레이션 할 수 있어야 합니다.

 

 

3.4.8 작업 집합 페이지 교체 알고리즘

참조 지역성 : 프로세스가 일부 페이지들을 집중적으로 참조하는 경향.

working set page replacement : 현재 참조하는 페이지들만 물리 메모리에 로드되어 실행

t : 시점, k : 페이지 개수. -> 시간이 지남에 따라 변화.

레퍼런스 비트에다가, 추가로 참조 시간을 기록해야함. 페이지 테이블 엔트리에 참조시간이 기록.

 

교체는 쭉 페이지 테이블을 스캔하다가 레퍼런스 비트가 1이면 0으로 바꾸고 참조시간을 현재로 변경.

이후 클록핸드가 다음 페이지를 검색. 타우 : 과거부터 현재까지의 윈도우로 주어짐 -> 이 윈도우보다 크면 더 이전에 참조된 거니까 해당 페이지를 교체.

만약 그런 페이지가 없다면 레퍼런스 비트를 0, 시간은 최대한 예전걸 기억 -> remember the smallest time.

이런식으로 작동하는게 워킹셋 페이지 교체.

 

3.4.9 워킹셋클록 페이지 교체 알고리즘 : 초기에 리스트는 비어 있음. 첫번째 페이지가 적재되면서 리스트에 추가 -> 쭉 이어서 링 구조 형성

 

clock의 이론적 베이스는 nru, 구현을 생각해보면 워킹셋 클록 알고리즘처럼 됨. 한바퀴 돌 때 그 페이지가 그 더티페이지를 디스크에 쓰는지 안쓰는지를 고려해야함

R = 1일 때, 0으로 바꾸고 클록핸드 증가 -> R=0일 때, 교체. 프레임에 적고 참조시간 적고 비트를 1로 만들고 클록핸드 증가.

 

구현불가하나 벤치마크시 상한으로 사용 -> optimal

이론적으로 잘 분석됨. 하드웨어로 쓸 수 없어서 lru처럼 동작시키려 했으나 잘안됨. -> nru

lru와 비슷하나 좀 더 잘 동작하는 것 -> nfu

순서대로 -> fifo, 첫 페이지 쫓아낼 수 있으니 기회 준 것 -> second chance

nru를 구현 -> clock

shift하면서 카운트 기록한 것 -> 에이징

이론적 워킹셋 알고리즘 구현한 것 -> wsclock.

성능 젤 좋을 것 같은 것 -> lru.