운영체제(9/11) - Virtual Memory 1,2

demand paging 

- 실제로 필요할 때 메모리에 올리는 것 

- 대부분의 경우에서 page fault는 잘 안남 

 

빈페이지가 없는 경우

- page replacement: 어떤 frame을 빼앗아올지 결정해야함 

- replace algorithm을 사용함: page-fault rate를 최소화하는 것이 목표 

 

optimal algorithm

- 미래의 가능성을 미리 안다는 가정에서 알고리즘(그래서 현실성이 떨어짐)

 

LRU(least recently used) 알고리즘 

- 가장 오래 전에 참조된 것을 지움 

- 예시) 가장 최근에 도둑질을 한 사람이 도둑질을 할 것이라고 생각함 

- 줄을 세워 하나씩 일일이 비교, 운영체제가 수행 

- paging system에서 사용 못함 

 

FIFO 알고리즘 

- 먼저 들어온 것을 먼저 참조 

 

LFU(least frequently used) 알고리즘 

- 참조 횟수가 가장 적은 페이지를 지움 

- 예시: 도둑질을 한 횟수가 적은 사람이 도둑질을 안할 것이라고 생각하기 

- 힙으로 구현 

- paging system에서 사용 못함 

 

다양한 캐슁(caching)환경 

- 캐슁 기법: 한정된 빠른공간(캐쉬)에 요청된 데이터를 저장해 두었다가 후속 요청 시 캐쉬로부터 직접 서비스하는 방식

- 캐슁 기법은 paging system 외에도 cache memory, buffer caching, web caching 등 다양한 곳에서 사용 \\\

 

clock algorithm 

- LRU의 근사 알고리즘 

- 사이클을 한바퀴 돌면서 레퍼런스가 1번도 없는 것을 없애는 방식, 돌면서 1인 것은 0으로 바꿈 

(포인터 이동하는 중에 reference bit이 1인 것은 0으로 바꾸고, 0인 것을 찾으면 페이지 교체 수행)

 

global vs local replacement 

- global replacement 

replace시 다른 process에 할당된 frame을 빼앗아 올 수 있다 

working set, PFF 알고리즘 사용 

예시: 먹을 것이 필요할 때마다 경쟁해서 배분함 

- local replacement

자신에게 할당된 frame내에서만 replacement 

FIFO, LRU, LFU 등의 알고리즘을 process별로 운영 

예시: 미리 먹을 것을 배분하고 각자 알아서 효율적으로 먹으라고 함 

 

Thrashing 

- 프로세스의 원활한 수행에 필요한 최소한의 paging frame 수를 할당받지 못한 경우 발생 

- page fault rate가 매우 높아짐 

- cpu utilization이 낮아짐, 시스템이 비효율적으로 됨 

 

working-set model 

- 프로세스의 working set전체가 메모리에 올라와 있어야 수행되고 아닐경우 모든 frame을 반납한 후 swap out

- locality of reference: 프로세스틑 특정 시간 동안 일정 장소만을 집중적으로 참조  

 

pff(page-fault frequency) scheme 

- page-fault rate의 상한값과 하한값을 둔다 

page fault rate가 상한값을 넘으면 frame에 더 할당 

page fault rate가 하한값 이하면 할당 frame 수를 줄임 

 

 

page size의 결정 

- 사이즈를 감소시키면 

페이지 수 증가 

페이지 테이블 크기 중가 

그래서 최근에는 페이지를 크게 하는 것이 트렌드