[week09] KOCW 운영체제(반효경교수님) - Virtual Memory 2

Virtual Memory 2

다양한 캐슁 환경

캐슁(caching) 기법

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

paging system 외에도 cache memory, buffer caching, web caching등 다양한 분야에서 사용

캐쉬 운영의 시간 제약

교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 없음

buffer caching이나 web caching의 경우

• O(1) ~ O(log n) 정도까지 허용

paging system인 경우

• page fault인 경우에만 OS가 관여함
• O(1)인 LRU의 list 조작조차 불가능 → 왜?(뒷부분에 자세한 설명 나옴)
• 페이지가 이미 메모리에 존재하는 경우 참조시각 등의 정보를 OS가 알 수 없음

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

운영체제가 참조 횟수가 가장 적은 놈을 알 수 있는가?

알 수 없다. ( ㄴOㄱ )

왜냐하면 메모리에 page 정보가 이미 있을 경우(page table에서 valid인 page를 사용할 때)는 운영체제에게 CPU가 넘어가지 않는다. 하드웨어적으로 주소변환을 해서 CPU가 읽어들인다. 그렇기 때문에 운영체제는 누가 얼만큼 참조되었는지 알 수 없다.

page fault가 발생해야 CPU의 제어권이 운영체제로 넘어오고, 운영체제는 disk에 있던 page가 메모리로 올라온 시간을 알 수 있다.

그래서 paging system에서는 운영체제에게 주어지는 정보가 반쪽만 주어지게 된다. 그래서 LRU의 linked list, LFU의 tree 자료구조의 조작을 운영체제가 하는건데 정보가 반쪽만 존재하므로 정확한 조작을 할 수 없다.

결론 : paging system에서는 LRU, LFU 알고리즘을 사용할 수 없다.

Clock Algorithm

paging system에서는 LRU, LFU 알고리즘을 사용할 수 없고, 일반적으로 clock algorithm을 쓴다.

Clock algorithm

LRU의 근사(approximation) 알고리즘

여러 명칭으로 불림

second chance algorithm
NUR(Not Used Recently) 또는 NRU(Not Recently Used)

알고리즘 진행과정

reference bit을 사용해서 교체 대상 page 선정(circular list)

hardware가 해당 page 참조시에 reference bit을 1로 변경해줌

reference bit이 0인 것을 찾을 때까지 포인터를 하나씩 앞으로 이동

포인터 이동하는 중에 포인터로 가리킨 reference bit 1은 모두 0으로 바꿈

한 바퀴 되돌아와서도(=second chance) 0이면 그 때 replace 당함

• 시계바늘이 한 바퀴 돌 때 참조가 한 번도 되지 않은 놈은 replace

자주 사용되는 page라면 second chance가 올 때 reference bit이 1(참조당함)이 될 것이다.

Clock algorithm의 개선

reference bit과 modified bit(dirty bit)을 함께 사용

reference bit = 1: 최근에 참조된 페이지

modified bit = 1 : 최근에 변경된 페이지(I/O를 동반하는 page)

• memory에서 올라온 이후로 page에 CPU가 write를 해서 내용이 바뀌었다는 의미.
• 따라서 replace될때 바로 지우면 안되고 backing store에도 그 내용을 수정해줘야 함
• modified bit이 1인 page는 replace 할 때 해야 할 일이 많으니까 되도록 replace 하지 않는 식으로 동작시키면 속도가 개선될 수 있다.

Page Frame의 Allocation

현재는 어떤 프로세스에 속한 page인지 무관하게, clock algorithm을 이용해서 쫓아내고 있다. 실제로 프로그램이 page fault를 잘 안내면서 원활하게 실행되기 위해서는 한 프로그램의 page들이 메모리에 같이 올라와 있어야 더 효율적이다.

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

Allocation의 필요성

메모리 참조 명령어 수행시 명령어, 데이터 등 여러 page 동시 참조

• 명령어 수행을 위해 최소한 할당되어야 하는 frame의 수가 있음

Loop을 구성하는 page들은 한꺼번에 allocate 되는 것이 유리함

• 최소한의 allocation이 없으면 매 loop마다 page fault가 발생

Allocation Scheme(어떻게 프로그램별로 page 개수를 할당해줄까?)

• equal allocation: 모든 프로세스에 똑같은 개수 할당
• proportional allocation: 프로세스 크기에 비례하여 할당
• priority allocation: 프로세스의 priority에 따라 다르게 할당

Global vs Local Replacement

사실, 이러한 할당을 해주지 않더라도 replacement 알고리즘을 사용하다보면 어느정도씩 할당하게 되는 효과가 있다.

Global replacement

• replace시 다른 프로세스에 할당된 frame을 빼앗아 올 수 있다.
• 프로세스별 할당량을 조절하는 또 다른 방법이다.
• FIFO, LRU, LFU 등의 알고리즘을 global replacement로 사용시에 해당
• working set, PFF 알고리즘 사용

Local replacement

• 자신에게 할당된 frame 내에서만 replacement
• FIFO, LRU, LFU등의 알고리즘을 process 별로 운영할 때

두 방법 모두 사용가능

Thrashing

메모리에 너무 많은 프로그램이 올라가서 발생하는 현상

Thrashing

• 프로세스의 원활한 수행에 필요한 최소한의 page frame 수를 할당 받지 못한 경우 발생
• page fault rate이 매우 높아짐
• CPU utilization이 낮아짐
• OS는 MPD(Multiprogramming degree)를 높여야 한다고 판단
• 또 다른 프로세스가 시스템에 추가됨(higher MPD)
• 프로세스당 할당된 frame의 수가 더욱 감소
• 프로세스는 page의 swap in / swap out으로 매우 바쁨
• 대부분의 시간에 CPU는 한가함
• low throughput

이 문제를 해결하기 위해서 degree of multiprogramming을 조절해 줘야 한다.

• working-set
• PFF(page-fault frequency)

Working-Set Model

Locality of reference

• 프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조(for 문을 도는 경우, 어떤 함수를 실행하는 경우 등...)
• 집중적으로 참조되는 해당 page들의 집합을 locality set이라고 함

Working-set model

• Locality에 기반하여 프로세스가 일정 시간동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 page들의 집합을 working set이라 정의
• working set 모델에서는 프로세스의 working set 전체가 메모리에 올라와 있어야 수행되고 그렇지 않을 경우 모든 frame을 반납한 후 disk로 swap out(suspend 상태가 됨)
• Thrashing 방지
• Multiprogramming degree 조절

Working-Set Algorithm

과거를 통해 working set을 추정하는 방식

Working set의 결정

• 현재시점부터 과거의 어떤 시점까지 window를 뚫어놓고 그 메모리는 working set으로 간주
• working set의 크기는 그때끄때 바뀜
• 참조된 후 delta 시간동안 해당 page를 메모리에 유지한 후 버림

Working-set algorithm

프로세스들의 working set size의 합이 page frame의 수보다 큰 경우

• 일부 프로세스를 swap out시켜 남은 프로세스의 working set을 우선적으로 충족시켜줌(MPD - multiprogramming degree를 줄임)
  Working set을 다 할당하고도 page frame이 남는 경우
• swap out 되었던 프로세스에게 working set을 할당(MPD를 키움)

Window size delta

• Working set을 제대로 탐지하기 위해서는 window size를 잘 결정해야 함
• delta 값이 너무 작으면 locality set을 모두 수용하지 못할 우려
• delta 값이 너무 크면 여러 규모의 locality set 수용
• delta 값이 무한대이면 전체 프로그램을 구성하는 page를 working set으로 간주

PFF(Page-Fault Frequency) Scheme

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

• page fault rate이 상한값을 넘으면 frame을 더 할당함
• page fault rate이 하한값 이하이면 할당 frame 수를 줄임

빈 frame이 없으면 일부 프로세스를 swap out

Thrashing 방지

Page Size의 결정

page size를 감소시키면

• page 수 증가
• page table 크기 증가
• internal fragmentation 감소
• disk transfer의 효율성 감소
  • disk가 찾는 시간(seek)이 늘어남
• 필요한 정보만 메모리에 올라와 메모리 이용이 효율적
  • locality의 활용 측면에서는 좋지 않음

Trend

• larger page size