[운영체제] KOCW 11.2 - Ch9: Virtual Memory

캐싱(Caching)

: 한정된 빠른 저장공간(캐시; physical memory)을 가지고 계속적으로 요청되는 새로운 객체를 저장공간(swap area; disk)에 읽어들였다가 후속 요청 시 직접 서비스하는 방식

 

▷ 캐싱 기법

• Paging system
• Cache memory
• Buffer caching
• Web caching

▷ 캐시 운영의 시간 제약

• O(n) -- Order of n(n번 비교)는 너무 많다.
• O(1) -- Order of 1(비교x) ~ O(log n) -- Order of (log n) 정도까지 허용

 

Clock Algorithm

※ LRU, LFU Algorithm: Paging system에서 이용 불가능하다.

<-- 이유: Page table이 invalid할 때는 운영체제가 개입하지만, valid할 때는 운영체제가 개입하지 않기 때문이다.

 

▶ Clock Algorithm( = Second chance algorithm, NUR(Not Used Recently), NRU(Not Recently Used)

: LRU(Leat Recently Used)의 근사 알고리즘

Clock Algorithm

• Reference bit = 0: 교체 대상 페이지 <-- by. 운영체제
• Reference bit = 1: 최근에 참조된 페이지(교체 대상x) <-- by. 하드웨어

1. reference bit = 0을 찾을 때까지 포인터를 하나씩 앞으로 이동한다.
2. 포인터를 이동하는 중에 reference bit = 1인 것은 모두 0으로 바꾼다.
3. reference bit = 0인 것을 찾으면 그 페이지를 교체한다.

※ Clock algorithm의 개선

: reference bit + modified bit을 이용한다.

• Reference bit = 0: 교체 대상 페이지
• Reference bit = 1: 최근에 참조된 페이지(교체 대상x)
• Modified bit = 1: 최근에 변경된 페이지 --> reference bit와 달리, clear하지 않는다. modified bit는 변경되었는지 확인하는 bit이기 때문이다.

--> Read: reference bit = 1로 설정한다.

--> Write: reference bit = 1, modified bit = 1로 설정한다. (Write: 변경)

 

---

Page Frame의 Allocation

※ Allocation: 각 프로세스에 얼마만큼의 page frame을 할당할 것인가?

 

▶ Allocation Schema

• Equal allocation: 모든 프로세스에 똑같은 개수의 page frame을 할당한다.
• Proportional allocation: 프로세스의 크기에 비례하여 page frame을 할당한다.
• Priority allocation: 프로세스의 priority에 따라 page frame을 할당한다.

 

▶ Global vs. Local replacement

• Global replacement: Replace 시, 다른 프로세스에 할당된 frame을 빼앗아올 수 있다.
• Local replacement: 자신에게 할당된 frame 내에서만 replacement한다.

 

Problem: Thrashing

• Thrashing: 프로세스의 원활한 수행에 필요한 최소한의 page frame 수를 할당받지 못하는 경우가 발생하는 것

Thrashing

▷ Thrashing의 원인

• 메모리에 올라가 있는 프로세스가 너무 많을 때, 프로세스 당 할당된 frame 수가 너무 적어서, page fault rate가 높아진다 --> CPU utilization이 낮아진다.
• 이때 운영체제는 프로세스가 너무 많다고 판단하지 못하고, 프로세스가 너무 적다고 판단하여 오히려 메모리 위의 프로세스 수를 늘리고, 프로세스 당 할당된 frame 수는 더욱 감소하여 상황이 악화된다.

 

Solution 1) Working-Set Algorithm

▷ Locality of reference

• 프로세스는 특정 시간동안 일정 장소만을 집중적으로 참조한다.

• Locality set: 집중적으로 참조되는 해당 page들의 집합

▶ Working-Set Model

• Working set: Locality에 기반하여 프로세스가 일정 시간동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 page들의 집합

• Working-Set model에서는 프로세스의 working set 전체가 메모리에 올라와 있어야 수행되고, 그렇지 않을 경우에는 모든 frame을 반납한 후 swap out(suspended)한다. (<--- 모아니면 도...)
• 따라서 working set size의 합이 page frame의 수보다 큰 경우: swap out --> 남은 프로세스의 working set을 우선적으로 충족시켜준다.

▶ Working set의 결정: working set window

--> working set window에 속한 page는 메모리를 유지하고, 속하지 않은 것은 버린다.

Working set window

 

Solution 2) PFF(Page-Fault Frequency) Scheme

PFF(Page-Fault Frequency) Scheme

▷ page-fault rate의 상한값과 하한값을 둔다. --> 적절한 page fault 비율을 유지한다.

• page-fault rate이 상한값을 넘으면, 할당 frame 수를 늘린다.
• page-fault rate이 하한값 이하이면, 할당 frame 수를 줄인다.

▷ page-fault rate이 상한값을 넘어서 할당 frame 수를 늘려야 하는데 빈 frame이 없다면, 일부 프로세스를 swap out한다.

 

 

Page Size의 결정

▷ Page size를 감소시키면,

• 단점: page table 엔트리 수가 증가하고, page table 크기가 증가한다.
• 단점: disk transfer 효율성이 감소한다. locality의 활용 측면에서 좋지 않다. (page fault 한번 당 읽어오는 page 양이 너무 적기 때문)
• 장점: internal fragmentation(내부조각; 물리적 메모리에서 할당되고 남는 공간)이 감소한다.

▷ 트렌드: larger page size!