운영체제의 기초 - 18. Demand Paging 2

Virtual Memory Management : Key Issues in Demand Paging

        

Demand paging: 페이지가 요구될 때 램에 불러오는 정책

이것이 꼭 좋은 방법은 아님 그 이유는 페이지가 요구되는 시점에서 램 레지던트하지 않아 요청하게 된다면 page fault가 일어나고 그 만큼 느린 디스크 latency(잠복) 맡게 되기 때문이다.

이상적인 Page Selection 정책

앞으로 사용될 Page를 미리 Main Memory로 가져와서 Page Fault가 발생하지 않도록 하는 것

가장 단순한 것이 Demand paging임 (=pure demand paging)

pure demand paging은 프로세스가 시작할 때 램에 0개의 page로 시작을 함.

entry point에 들어가면서 첫 instruction에서 page fault가 발생하며 한 페이지가 읽어들이게 되고

걔가 data page를 access하게 되면 또 fault가 발생하고 

초반에는 엄청난 page fault를 야기시켰다가 어느 순간 충분한 page가 들어오게 되면 원활하게 도는 것.

가장 단순하게 생각할 수 있지만 이것은 문제가 있음

프로세스가 생성이 되서 시작을 할 때 너무 오랜 시간이 소요된다는 단점이 있음

Demand Paging의 문제 해결 방안

Prepaging: 앞으로 사용될 Page를 예측해서 미리 Main Memory로 로드하는 기법

예를 들면, 한 페이지가 요청이 됐으면 그 다음 페이지도 미리 읽어들이는 것

효과적인 Prepaging 방안

Spatial Locality에 기반하여 Page Fault가 발생한 근처에 있는 Page들을 Main Memory로 로드

인접한 페이지 1페이지만 읽어들일 것인가? 아니면 4페이지를 읽어들일 것인가? 더 많이 할 것인가?

이런 것들을 결정해야 함

OS은 발생하지 않은 미래를 예측해야 하기 때문에 어쩔 수 없이 운영 노하우가 들어가게 됨 (admin이 결정해야 할 이슈)

요즘에는 많이 사용되지 않으나 prepaging과 비슷한 것이 있음

Request paging

논리적으로 연관성이 있는 Page들을 미리 Main Memory로 로드하는 기법

예를 들어서 어떤 프로그램이 4개의 modual로 구성이 되어있다 

수행시켜봤더니 A modual이 수행이 될 때는 꼭 D에 있는 서브루틴을 호출하고

B modual이 수행이 될 때는 C modual을 호출하더라 (이런 것들을 프로그래머가 안다고 가정하여)

grouping을 해서 B modual이 올라갈 때는 C modual까지 미리 올리는 것임

일종의 prepaging인데 단순하게 인근 페이지를 올리는 것이 아니라 논리적인 연관성이 있는 것들을 올리는 것임

아주 작은 메모리를 MMU에 지원이 없이 Demand paging하기 위해서 사용한 것이 Request paging임

다른 말로 Overlay라고 부름

A와 D가 메모리에 돌다가 B가 올라가게 되면 A와 D를 다 지워버리고 그 위에 B와 C를 overlay하기 때문에

요즘에는 많이 사용하지 않음 Demand paging을 지원하는 MMU가 사용되고 있기 때문이다.

프로그램의 속성을 사용자가 규정해 줘야한다는 문제가 있음 그래서 OS가 알아서 해주면 좋겠음

어떤 페이지가 사용되면 그 외에 다른 어떤 페이지들이 함께 사용된다는 것을 OS이 스스로 알아서 올려주면 좋겠음

그런 개념이 바로 Working Set 임

working set을 통해 prepaging과 request paging을 결합한 그리고 OS이 자동적으로 처리해주는 page selection policy를 사용하게 됨

Virtual Memory Management : Page Replacement Policies 1

      

페이지 교체 정책

Demand paging 중에 가장 중요한 부분임 (효과가 가장 크기 때문)

1. Random

memory replacement를 H/W적으로 구현할 때 잘 동작함

지금까지 page replacement를 S/W적으로 OS 코드로 구현하는 것을 생각하니까 복잡한 policy를 고민하게 되지만

예를들어 Cache line replacement를 한다고 했을 때는 Random을 많이 사용함

2. FIFO

흔히 많이 사용하는 방식 FIFO 

3. OPT (optimal)

어떤 것을 내보내는 것이 optimal일까? 가장 먼 미래동안 전혀 사용되지 않는 페이지를 골라서 내보내는 것

페이지 교체 알고리즘을 개발했을 때 성능 비교를 하기 위해서 많이 사용된다.

물론 비교하기 위해서는 어떤 페이지들이 어떤 순서대로 access되는가에 대한 input이 있어야 함

그런 input을 reference string이라고 함 (1page-5page-100page-50page access된 페이지들을 순서대로 나열한 sequence)

Reference String: Sequenced of Referenced Pages

어디서 얻어올까? 벤치마크 프로그램을 돌려 각 페이지들이 access될 때마다 다 로그를 남겨서 그것을 얻어오게 됨

이러한 로그를 미리 다 알고 있다면 optimal을 구현할 수 있게 됨

4. LRU (Least Recently Used)

가장 중요한 페이지 교체 정책 (최근에 가장 사용되지 않은 페이지를 골라서 내보내는 것)

Locality(지역성) 때문임. 프로그램의 수행에 Spatial Locality가 있기 때문에 

지금 사용되는 페이지들은 가까운 미래에도 사용될 것이고

최근에 사용되지 않았던 페이지들은 Temporal Locality 때문에 미래에도 사용되지 않을 것이다.

LRU (Least Recently Used) Algorithm

Temporal Locality에 기반한 Page Replacement 정책

정리

OPT 어차피 할 수 없는 것

Random은 H/W 적으로 replacement policy를 구현할 때만 사용함. S/W 적으로 더 잘만들 수 있기 때문에 사용X

실제로 많이 사용되는 것은 FIFO와 LRU 알고리즘임

a

FIFO는 page frame들을 전부 Queue로 link-list 만들어서 사용 (구현이 쉬움)

LRU는 모든 페이지들이 언제 최종적으로 reference 됐는지를 다 기록해야 함 (Timestamp를 찍음)

Timestamp를 찍는다는 것은 (RAM의 Physical memory의) page frame 하나하나마다 counter register들을 다 하나씩 두어야 한다는 의미임

그래서 어떤 페이지가 reference되면 그 때 Timestamp 값을 읽어와서 계속 기록 해야됨

실제로 이렇게 구현이 될까? Nope 하드웨어적 오버헤드가 너무 큼 

그래서 실제로는 

Counter를 둔다는 것은 굉장히 거창한 일이지만 이미 page들(memory에 resident한 page)에 대해서는 여러가지 bit 플래그를 가지고 있다고 말했잖아요?

transaction lookaside buffer (TLB)를 공부할 때 cache line entry를 보여줬음. 어떤 플래그 bit들이 있었죠? (캐쉬됐냐 안됐냐 / 맵됐냐 안됐냐 / 메모리 레지던트하냐 하지않냐 이런 bit들) 참고: http://ergate.tistory.com/206

별도의 테이블이 있으니까 거기에 timer, Timestamp를 찍을 수 있는 register값까지 두기에는 문제가 심각하지만 bit 값을 넣을 수 있는 여지는 있음

counter를 두는 대신에 1bit를 주고 어떤 페이지가 access되면 걔를 1로 세팅하고 access 되지 않으면 0으로 설정하는 Reference bit을 두게 됨

Reference Bit (Use Bit)

Main Memory에 로드된 Page가 Access되면 Set되는 Bit Flag

메모리 관리를 할 때 굉장히 중요한 H/W 적 서포트가 있는데 그것이 2개의 Bit (flag bit)임

1. Resident Bit: S/W적으로도 얼마든지 구현이 가능함

2. Reference Bit (Use bit): 

내가 사용하려고 하는 페이지가 램에 있으면 페이지테이블 entry가 valid하게 존재할 것이고 Resident bit 을 1로 세팅함

그 entry에 있는 frame number는 valid한 값이어서 frame number를 통해서 페이지테이블의 physical location을 찾아낼 수 있음

만약 Resident bit이 0라면 swap device에 있으니 swap space에 주소를 별도로 저장하고 access할 수 있게 저장해야 함

Reference Bit은 S/W적으로 구현이 가능하지만 H/W적으로 서포트가 됩니다.

어떤 페이지가 램에 resident 할 때 access했을 경우 H/W적으로 '1'로 세팅해줌

reference bit을 이용해서 LRU 알고리즘을 구현함

LRU를 비교하려면 시간을 비교해야 하기 때문에 timestamp full value를 가지고 있어야 하는데 1bit 밖에 안가지고 있음

그렇기 때문에 LRU를 100% 구현은 못하고 approximation(근사치)을 할 수 있다.

optimal 알고리즘을 approximation하는 것이 LRU인데 LRU를 구현하는 것 역시 H/W적으로 비용이 너무 비싸서 approximation 함

대부분의 모든 OS은 LRU approximation 알고리즘을 가지고 있음

reference string: 어떤 프로세스가 수행을 하는데 refer했던 페이지들의 시퀀스 

사람들이 FIFO를 좋아함 왜? 구현하기가 쉬움 link-list만 구성하고 있으면 됨

상식적인 문제 말고 FIFO에 가장 나쁜 문제가 있다는 것을 찾아냄 (Belady's anomaly)

Belady's Anomaly

Memory를 눌렀음에도 불구하고 Page Fault가 더 많이 발생하는 현상

언제나 나쁜 Belady's Anomaly를 보이는 것은 아님 극단적인 예일뿐.

절대 anomaly를 나타내지 않는 알고리즘의 그룹을 grouping하여 stack algorithms이라고 불렀음

왜? stack algorithm? 

Stack Algorithm

N개의 Frame으로 구성된 Memory에 로드된 Page들이 항상 

N+1개의 Frame으로 구성된 Memory에 로드된 page들의 부분집합이 되는 Algorithm

Belady's Anomaly가 절대 발생하지 않음

대표적으로 LRU 알고리즘이 있음

가장 오래된 것 (오랫동안 사용되지 않은 것)들만 왔다갔다 하지 나머지 string들은 항상 서브스트링으로 존재하기 때문

하지만 FIFO는 그런 관계를 증명할 수 없음 (들어오는 것과 나가는 것이 분리되어 있기 때문)

* FIFO를 사용하는 사람들에게 사용하지 말라는 취지가 됨

LRU는 H/W적 오버헤드가 있음 (timestamp/counter를 다 붙여야 하기 때문)

사람들이 처음에는 실제로 다 붙이려고 했음

문제: 각 페이지 frame에 붙여야 되는 counter에 크기를 얼마나 해야될까?

만약 어떤 시스템이 long running하는 시스템이라고 하면 counter값이 점점점점 커질 거임

오버플로우가 나면 오래됐음에도 불구하고 작은 값을 갖게됨

이런 문제가 생기기 때문에 approximation을 하게 됨

1. Reference bit를 1개 두고 8bit짜리를 하나씩 붙여서 일정한 간격으로 reference bit을 shift light 시킴 

어떤 놈이 제일 사용안된 놈인지를 판단하기 위해 레지스터 값들을 전부 비교하여 

가장 작은 값의 page frame을 골라서 replace하는 것을 사용했음

단점: 각 페이지 프레임마다 shift 레지스터값을 붙여야 된다는 비용에 비해서 크게 효과적이지 않음

2. reference bit 만을 사용하자!

reference bit도 1bit 레지스터라고 볼 수 있음 (1bit 레지스터로 타임을 다 기록하기에는 어려움)

시간을 일정한 interval로 나누고 그 interval에서만 사용된적 있니 없니를 비교하는 것임

OS는 page replace를 하기 위혀서 매 interval 마다 모든 reference bit 들을 리셋시켜야 함. 

리셋 시키기 전에 교체를 해야 한다면 1인 놈을 찾아서 내보내는 기법임

이러한 알고리즘을 조금 더 체계화 시킨 것이 Clock 알고리즘임.

clock hand가 필요함 (현재 가리키고 있는 임의의 페이지)

페이지를 교체해야할 시기가 오면 clock hand를 움직여 어느페이지를 선택할지 결정한다.

UNIX OS에서 많이 사용하는 기법임

Clock Algorithm에서 교체할 Page를 선택하는 방법

Clock Hand가 가리키는 Page의 Reference Bit이 1인 경우, 0으로 바꾸고 Clock Hand가 다음 Page를 가리키도록 한다.

이 과정을 반복하다가 Reference Bit이 0인 Page를 만나면 해당 Page를 교체한다.

OS이 지금 내가 과부화가 걸렸는지 확인하는 방법은 Clock Hand가 얼마나 빨리 돌고 있는가이다.

모든 page reference bit가 1이라 스킵을 해야 한다면 한바뀌 다 돈다음에 어떻게 해야 할까?

Clock알고리즘은 LRU approximation인데 physical memory가 over permit되어있으면 FIFO 알고리즘으로 degenerate 된다 

이것이 가장 대표적인 LRU 기반의 replacement 알고리즘이다.

Enhanced clock algorithm

Reference bit만 가지고 선택을 했는데 그러지 말고 dirty bit도 보자는 기법임

쫓아낼 때 clean page를 쫓아내고 싶은가? dirty page를 쫓아내고 싶은가? clean page (swap device에 쓸 필요가 없기 때문)

reference가 안됐고 clean한 놈 > reference가 안됐고 dirty한 놈 > reference가 됐고 clean한 놈 > reference가 됐고 dirty한 놈

페이지들을 고름 (위에 왼쪽부터 순서대로 고름)

이것 또한 heuristics(corner case)이 생김  EX) clean page를 내보낼 때 항상 옳을까? 

레퍼런스 bit 하나만 가지고 LRU를 정확히 모델링을 할 수 없기 때문에 발생함

이런 것에 대응하는 요소들이 알고리즘에 첨가가 되기 때문에 실제로 page reference 알고리즘이 구현된 OS부분은 상당히 복잡해질 수 있음

시스템 admin이라면 시스템의 메모리가 어떻게 사용되는지 관심을 가질 필요가 있음

왜냐하면 성능에 굉장히 큰 영향을 주기 때문이다. 

UNIX계열의 OS은 메모리들의 상태를 분석할 수 있는 도구들을 많이 정의해 줌

# sr : clock hand가 얼마나 자주 돌고 있는가? 초당 얼마나 돌고 있는가

# vmstat : 일정한 시간 간격동안 현재 clock hand가 몇번 회전했으며 free page가 얼마며 이런 정보를 제공해 줌

이러한 통계 커멘드를 함께 사용할 수 있음

Page Replacement Policies 2

Reference bit H/W가 제공하지 않는 core 아키텍처일 경우 FIFO replace 기법을 사용한다.

FIFO의 기법만으로는 여러가지 부작용이 발생하기 때문에  Frame buffering 사용한다.

FIFO + Frame buffering = clock 알고리즘과 유사한 좋은 성능을 얻어 낼 수 있음

Frame buffering은 캐시 메모리관리에서도 많이 사용함

page replacement style = page allocation style

---

출처 - http://snui.snu.ac.kr/ocw/index.php?mode=view&id=674

출처 - http://snui.snu.ac.kr/ocw/index.php?mode=view&id=675

출처 - http://snui.snu.ac.kr/ocw/index.php?mode=view&id=676