다양한 캐슁 환경

• 캐슁 기법
  한정된 빠른 공간(=캐쉬)에 요청된 데이터를 저장해두었다가, 후속 요청시 캐쉬로부터 직접 서비스하는 방식
  paging system 외에도 cache memory, buffer caching, Web caching 등 다양한 분야에서 사용.

• 캐쉬 운영의 시간 제약
  교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 없음
  Buffer caching이나 web caching의 경우 -> O(1) ~ O(log n) 정도까지 허용
  Paging system 인 경우 -> page fault인 경우에만 OS가 관여함. 페이지가 이미 메모리에 존재하는 경우 참조시각 등의 정보를 OS가 알 수 없음. O(1)인 LRU 의 list 조작조차 불가능

Paging system에서 LRU, LFU 가능한가?

주소변환 과정은 하드웨어 기반으로 이루어져서 운영체제가 어떤 프로세스를 줄세우고 순서를 주는것이 불가능.
그래서 나온 것이 clock algorithm

Clock algorithm

모든 페이지에 사용시각을 운영체제가 알 수 없기때문에 비트 하나만 가지고 쫓아낼 페이지를 결정.

• LRU의 근사 알고리즘
• Second chance algorithm, NRU(Not Recently Used)로도 부름.
• Reference bit을 사용하여 교체 대상 페이지 선정(circular list)
• reference bit가 0인 것을 찾을때까지 포인터를 하나씩 앞으로 이동
• 포인터 이동하는 중에 reference bit 1 은 모두 0으로 바꿈
• reference bit이 0인 것을 찾으면 그 페이지를 교체
• 한 바퀴 되돌아와서도 (=second chance) 0이면 그 때에는 replace 당함.
• 자주 사용되는 페이지라면 second chance가 올 때 1.

Clock algorithm의 개선

• reference bit(access bit)과 modified bit(dirty bit)을 함께 사용
• reference bit = 1 : 최근에 참조된 페이지 -> 쫓아낼지 말지를 결정하는 비트
• modified bit = 1 : 최근에 변경된 페이지 (I/O를 동반하는 페이지) -> 수정되었다면 변경된 내용을 디스크에 써줘야함

bit을 on/off 하는 것은 하드웨어의 지원을 받아 운영체제가 프로세스를 쫓아내는 것을 결정한다.

Page Frame의 allocation

• Allocation problem: 각 프로세스에 얼만큼의 페이지 프레임을 할당해줄 것인가?
• Allocation의 필요성
  메모리 참조 명령어 수행시 명령어, 데이터 등 여러 페이지 동시 참조. 명령어 수행을 위해 최소한 할당되어야 하는 frame의 수가 있음.
  Loop를 구성하는 페이지들은 한꺼번에 할당되는 것이 유리함.
  최소한의 allocation이 없으면 매 루프마다 page fault 발생
• Allocation Scheme
  1. Equal allocation: 모든 프로세스에 똑같은 갯수 할당.
  2. Proportional allocation: 프로세스 크기에 비례하여 할당
  3. Priority allocation: 프로세스의 Priority에 따라 다르게 할당.

Global vs Local Replacement

• Global replacement
  Replace 시 다른 프로세스에 할당된 프레임을 빼앗아올 수 있다.
  프로세스 별 할당량을 조절하는 또 다른 방법.
  FIFO, LRU, LFU 등의 알고리즘을 Global replacement로 사용 시 해당.
  Working set, PFF 알고리즘 사용
  프로세스 간 무한 경쟁 방식

• Local replacement
  자신에게 할당된 프레임 내에서만 replacement
  FIFO, LRU, LFU 등의 알고리즘을 프로세스 별로 운영시.

메모리에 너무 많은 프로그램을 동시에 올리면, 프로세스가 원활히 실행되기 위한 최소한의 메모리를 얻지 못해서 페이지 폴트가 과도하게 발생하면 Thrashing 발생.
-> CPU는 놀고, 페이지폴트가 주구장창 발생.

Thrashing

• 프로세스의 원활한 수행에 필요한 최소한의 페이지 프레임 수를 할당받지 못한 경우 발생
• Page fault rate가 매우 높아짐
• CPU utilization이 낮아짐.
• OS는 MPD(Multiprogramming degree)를 높여야 한다고 판단하여 더 많은 프로세스를 추가투입.
• 프로세스 당 할당된 프레임 수가 더욱 감소
• 프로세스는 페이지의 swapping 진행으로 매우 바쁨
• 대부분의 시간 CPU 는 매우 한가함.
  -> Low throughput

프로그램한테 필요한 최소한의 메모리는 보장해주어야 쓰레슁을 피할 수 있다.

Working-Set Model

• Locality of reference
  프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조한다.
  집중적으로 참조되는 해당 페이지들의 집합을 Locality set이라 함.
  이들은 페이지 프레임의 충분한 양을 보장하여 원활히 실행되게 한다.

• Working-Set Model
  Locality에 기반하여 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 페이지들의 집합을 Working Set이라 정의함.

Working Set 모델에서는 프로세스의 working set 전체가 메모리에 올라와 있어야 수행되고 그렇지 않을 경우 모든 프레임을 반납한 후 swap out -> suspended.

추후 메모리가 남아돌 때 전체 working set이 메모리에 올라올 수 있게되면 그때부터 메모리에 올라와 실행.

Thrashing을 방지함.

Multiprogramming degree를 결정함.

메모리가 충분하여 Working set을 보장받을 수 있는 프로그램만 메모리에 올리고 그렇지 않으면 스왑아웃해둔다 -> Thrashing을 방지.

PFF (Page-Fault Frequency)

• page-fault rate의 상한과 하한을 둔다.
  => 상한값을 넘으면 적은 페이지 프레임이 할당된 것으로 간주하고, 프레임을 더 할당한다.
  => 하한값보다 작으면 너무 많은 프레임이 할당된 것으로 간주하여, 할당 프레임을 줄인다.

Page size의 결정

32비트 메모리 주소 체계에서는 페이지 사이즈를 일반적으로 4KB.
하지만 점점 프로그램이 커지고, 64비트 주소체계가 등장함에 따라 메모리에 들어가는 페이지 수가 많아짐.

전체 메모리가 커지면서 메모리를 쪼개 쓰는 페이지의 크기도 좀더 커지게 된다.

• Page size를 감소(잘게 썰면)시키면,

1. 페이지 수 증가
2. 페이지 테이블 크기 증가
3. internal fragmentation 감소. 메모리 공간 효율적 사용.
4. Disk transfer 효율 감소: Seek/Rotation vs transfer
5. 필요한 정보만 메모리에 올라와 메모리 이용이 효율적 : Locality의 활용 측면에서는 좋지 않음.

• Trend : Larger page size. -> page fault 수 감소