운영체제의 기초 - 17. Demand Paging 1

Why Demand Paging?

지난 시간까지 공부한 내용들은 프로세스 메모리 관리 관점에서 보면 약간의 기계적인 요소들임

Demand Paging이란?

메모리 관리 메커니즘(MMU 메커니즘)을 사용해서 여러 프로세스가 시스템의 메모리를 효율적으로 공유할 수 있도록 하는 기술

Agenda

- Background

- Issues

- Thrashing and working Set

- Miscellaneous Issues

- Conclusion

지금까지 배웠던 메카니즘의 가장 큰 특징은? (MMU가 존재함으로써 기여됐던 점)

MMU가 들어옴으로 인해서 physical memory와는 별도로 logical memory가 생김

이것이 가장 큰 특징이자 장점임

physical memory space라는 것은 컴퓨터 시스템 각 instance마다 다 다름

컴퓨터 installation마다 다 다름 다양한 모습을 가지고 있는데 

이것과 무관한 logical address space를 도입해 준 것이 MMU 메커니즘에 가장 큰 특징이 임

매핑을 시켜준 다는 것. 새로운 어떤 가상적인 space를 제공해 주다는 것은 또 무엇을 의미하냐면

논리적인 주소공간을 물리적인 주소공간으로 변환시켜준다는 의미도 있음

어쨌든 지금까지 배웠던 것들은 매커니즘이다.

또 하나는 구체적으로 말하지는 않았지만 암암리에 얘기된 것은

어떤 유저프로그램이 컴퓨터 시스템에서 돌려면 걔가 필요로 하는 메모리들 (ex. code segment/data segment/stack segment)

이런 것들이 모두 physical memory에 다 있어야 된다라는 가정하에서 지금까지 설명했음

위의 가정이 필요할까? 필요하지 않을까? 

Q. 프로그램이 필요로 하는 모든 메모리(Code Segment, Data Segment, Stack Segment)가 Physical Memory에 있어야 하는가?

A. 그렇지 않다. 왜냐하면 프로그램은 Locality(집약성)를 가지고 있기 때문이다.

Principle of Locality (Locality of Reference)란?

프로그램이 가장 최근에 접근했던 데이터를 다시 접근(Temporal Locality)하거나, 최근에 참조했던 데이터 근처의 주소를 참조(Spatial Locality)하는 경향이 있음.

한 프로세스가 수행하고 있으면 현재 수행되는 instruction들 또는 현재 access되는 데이터들 주변에 있는 페이지들이 집중적으로 access됨 (locality를 보임) locality의 근거는? 어떤 학자가 실험을 통해 조사를 해봤더니 프로그램의 임의의 순간에 세워봤다 프로그램이 10%의 고정된 공간에 항상 있더라 90% 이상의 시간에 왜그럴까? 루프때문임 루프를 수행하면 루프를 다 빠져나오기 전까진 계속 머물러 있어야 되기 때문

90/10 Rule

불과 10%의 코드가 프로그램 총 수행시간의 90%를 차지함

locality 특성을 가지면 프로세스가 필요로 하는 모든 공간을 physical memory allocation할 필요가 없음

그렇다면 우리가 생각해 볼 점이 있음

현재 logical address space에 있는 page들 중에서 physical memory에 있지 않은 놈은 어디에 있어야 될까?

swap device 또는 swap space 에 있어야 함

swap과 disk의 차이점은? 또는 file system

- disk에 있는 데이터들, disk에 있는 named correction of data를 file이라고 함

swap이라고 하는 것은 file하고 비교해서 생각할 수 있음

file을 직접 access하는 것은 굉장히 오래 걸리는 operation입니다.

그런데 swap device는 파일에 한 부분으로 놓게 되면 오래 걸리니까

direct access가 가능한 low device로 별도로 access할 수 있게 만든다. (swap device는 low disk block이다.)

Swap Area (Swap Device)란?

Physical Memory 에 저장되지 못한 page들을 저장하는 디스크의 공간으로 File에 비해 운영체제가 직접 빠르게 접근할 수 있음 (logically swap device라고도 말함.)

Swap Device가 가득 차는 경우 예외적으로 File을 만들어서 Page들을 저장할 수도 있음

Q. Physical Memory에서 Swap Device로 Write Back하는 일이 언제 발생하는가?

A. 새로운 Page를 Physical Memory에 저장해야 하는데 빈 공간이 없고, Physical Memory에서 쫓아내려는 Page가 Dirty Page(그 동안 수행중에 modify 됐다)인 경우

swap device와 physical memory 사이에는 memory transfer operation이 발생하는데 이런 것은 덜 발생하는 것이 좋다

어떻게하면 두 메모리 사이에 operation들이 block transfer operation이 발생하지 않게 만드느냐?

Demand Paging Policy의 목적

Physical Memory와 Swap Device 사이의 데이터 전송이 최소한으로 발생하도록 함

Jim Gray

Memory Access Latency 

레지스터(1사이클) < L1캐시(수사이클) < L2캐시(수십사이클) < Main Memory(수백사이클) < Disk(수백만사이클)

굉장히 좋은 MMU 메커니즘을 가지고 있어도 (교내에서 해결해도 되는 문제인데) 그것을 운영하는 Policy가 좋지 않으면 매번 달나라를 갔다와야 하는 문제가 발생할 수 있음

달나라에 갔다오는 상황을 Thrashing이라고 말함

Thrashing이란?

프로세스들이 사용하는 Page들의 크기보다 사용가능한 Physical Memory의 크기가 작을 때, 사용하려고 Swap-in 하는 Page에 의해 앞으로 사용할 Page가 Swap-out 되면서 반복적으로 Page Fault가 일어나는 현상

(실제로 초창기 time sharing OS이 등장했을 때 심각한 문제로 나타났음)

정리

우리가 공부하려고 하는 것은 Demand Paging임

Demand Paging이라는 것은 어떤 프로스세가 수행하려는데 locality 때문에 집중적으로 access되는 page들만 읽어들이는 것

언제? on demand로 필요할 때

Demand Paging을 잘하느냐에 따라 우리가 달나라를 가야만 하느냐? 교내에서 해결할 수 있느냐? 문제로 귀착시킬 수 있음

지금까지는 Logical address가 나오면 Physical address로 translation했는데 

physical address가 RAM address에만 있었음 그러나

이제는 I/O device 즉 swap device로 가는 address도 있다.

demand paging을 할 때는 logical address space라는 용어보다는 virtual address space라는 용어를 더 많이 씀

이 두가지 용어가 뭐가 다를까?

virtual address space는 실제 컴퓨터 시스템이 크지 않는 physical memory를 가지고 있어도 자기보다 훨씬 큰 유저프로세스를 받아들일 수 있는 것

존재하지 않은 physical memory를 표현하는 address space이다.

완전히 없는 것을 제공해 줄 수 없으니 physical memory의 부족한 부분은 swap device에 가게 됨

이제 우리가 공부할 것은 virtual address를 어떻게 physical address로 변환을 시키느냐?

우리의 바람은 virtual address가 physical address로 변환이 될 때 swap device보다 RAM에 들어가기를 원함

즉, swap device를 access해야 되는 횟수를 가장 최대한 줄이면 됨

이상적인 Demand Paging의 동작

앞으로 사용될 페이지와 사용되지 않을 페이지를 미리 알아서 Physical Memory로 불러들이거나 Swap Device로 내보내는 것 (Clairvoyant Replacement Algorithm)

Page table entry가 virtual memory management를 지원하려면 과거와는 약간 다른 정보가 있어야 함

- 타겟주소가 RAM이 아닐 때, 다시말해서 메모리에 resident(상주)하지 않을 때 현재 메모리에 없다라는 것을 표현해 주는 플래그가 있어야 함

- 그리고 Residence bit가 off 되어있을 때 swap device에 주소를 찾을 수 있는 방법을 page table에서 가지고 있어야 함

Residence Bit

대상 페이지가 Physical Memory에 있는지 Swap Device에 있는지 표시하는 Page Table의 플래그

근거가 뭘까? Disk 같은 secondary device는 값이 굉장히 싸다 대신 느림

그런데 예지력을 가지고 Demand paging을 잘 운영하면 모든 일을 background에서 다 처리하기 때문에 

실제로 Disk에 싼 스토리지를 이용해서 High speed 메모리처럼 사용하는 것임

이것이 virtual memory의 가장 큰 key임

그런데 이런 희망이 무너지게 되면 매번 메모리를 access하기 위해서 디스크를 access해야 하는 상황이 발생하게 됨

이것이 Demand Paging이 무너진 상황이고 이때 발생하는 것이 Thrashing이다.

Demand Paging이 가능한 이유는? locality 때문임 (Temporal Locality와 Spatial Locality가 있다고 했음)

Page Fault Handling 

Demand Paging을 하려면 중요한 기술적 이슈들을 몇 가지 언급해야 함

가장 대표적인 기술적 이슈가 Page Fault Handling 입니다.

Page Fault가 무엇인가?

Fault라는 것은 interrupt 때 배웠음

interrupt는 크게 H/W interrupt와 S/W interrupt로 나눠짐

S/W interrupt 다른 여러가지 이름으로 부르는데 Trap, Fault, inception 있음

Fault는 주로 S/W적으로 문제가 생긴 것을 의미함

어떻게 하면 프로세스가 진행할 수 없을까?

Virtual Address reference를 날렸는데 그 타겟 페이지가 resident하지 않아 더 이상 수행할 수 없을 때 page fault라고 해서 S/W interrupt를 발생시킴

Page Fault란?

Virtual Address가 가리키는 Page가 Physical Memory에 없어서 프로세스가 더 이상 진행할 수 없는 상태를 운영체제에게 알려주는 인터럽트

page fault가 뜨면 OS은 당연히 뭘 해야할까?

interrupt니까 ISR이 떠야 되겠죠? 그것을 Page Fault Handler 라고 말합니다.

Page Fault Handler가 뜰 때는 당연히 그 Fault를 만든 프로세스의 수행은 중단 시키게 됨

그리고 걔의 Context들을 전부 save합니다. 그리고 그 프로세스는 결국 block상태로 감 (sleep상태)

왜냐? Disk operation을 끝나기를 기다려야 하기 때문이다.

Disk operation은 시간이 굉장히 오래걸리니 그 때 CPU를 점유하고 있으면 안되겠죠?

이와같이 현재 수행 중인 프로세스가 block이 되고 page fault handler가 뜨게 됩니다.

page fault handler는 DMA controller에게 해당 페이지의 주소를 던져주고 DMA를 initiation(개시,시작) 함

swap device에서 physical memory로 쫙~ 페이지를 읽어들이게 됨

     

Page Fault Handler의 동작

1. DMA Controller에게 해당 Page의 주소를 전달

2. DMA Controller는 해당 Page를 Physical Memory로 로드

3. DMA Controller의 작업이 끝나면 인터럽트 발생

4. 운영체제는 Page Fault를 일으킨 프로세스의 수행을 재개

어떻게 페이지가 없는줄 알까?

Present bit 또는 valid bit 이라고 하는 비트를 페이지 테이블 엔트리에서 확인함으로써 알 수가 있게 됨

그리고 Page Fault는 언제 뜨느냐?

위의 bit가 off 되어있을 때고 그것의 결과로 OS ISR이 돌게 된다.

지금까지는 인터럽트가 발생했을 때 처리해야하는 평이한 스토리임

그런데 여기에는 생각만큼 평이하지 않은 내용이 들어가 있음

Page Fault Handling에 어려운 이슈가 있다. 그것이 무엇일까?

Hint

- interrupt가 인지되는 시점은? 인터럽트 시그널이 걸리면 바로 인지가 되나요? 약간 딜레이가 있다고 했음

- 그것이 언제인가? instruction 수행중에 인지하는가? 그렇지는 않음

- instruction의 수행이 다 종료되고 난 후 새로운 instruction이 수행되기 직전에 그때만 interrupt를 인지함

- 왜 그럴까? 만약에 instruction 수행중간에 interrupt를 인지해서 바로 끝내면 머신 state가 애매모호하게 될 수도 있다.

- 그리고 그 instruction은 restart 해야 함. 그런데 반복하는 것이 항상 가능한 것은 아님

Page Fault의 처리가 다른 인터럽트에 비해 어려운 이유

수행 중인 instruction에 의해 변화된 상태를 되돌렸다가 Page Fault 처리가 끝난 후 해당 Instruction을 재개해야 하기 때문

항상 반복되지 않는 예를 들면 auto increment 와 auto decrement instruction이 있음 -->  MOVE (SP)+,-(R2) 

Stack pointer가 가리키고 있는 memory location의 값을 R2라는 레지스터가 가리키고 있는 memory location으로 copy해라 (MOVE하라는 instruction임)

그 직전에 R2의 값을 한 워드만큼 감소시키고(포인터 값을 하나 빼고) 그 값을 넣어라

이런 instruction이 수행 중간에 중지됐다고 생각해 보면 auto decrement가 수행 직전에 중지됐는지 직후에 중지됐는지에 따라서 어떻게 restart 해야하는지 달라지겠죠 이것까지 전부다 trace(찾아내다)할 수는 없음. 왜냐하면 instruction이 CPU입장에서 보면 수행의 최소단위기 때문에

So, 우리가 interrupt를 인지할 때는 instruction의 수행이 다 끝나고 함

단 예외가 있음 Page Fault일 경우임. instruction이 수행할 때 memory reference가 언제 날아가죠? 최소한 1번, 많으면 2~4번까지 날아감

최소한 1번은 그 instruction을 Patch할 때, 그리고 또 언제 날아가요? 메모리를 access할 때 등 

매번 memory reference마다 page fault가 발생할 수 있음

그러니 Stack pointer가 가지고 있는 메모리를 access할 때도 page fault가 발생할 수 있고 R2 레지스터가 가리키고 있는 memory reference할 때도 page fault가 발생할 수 있음 이런 상황에서는 우리가 restart하기가 굉장히 어려움

그렇다면 어떻게 하면 될까?

뭐라고 하는지 모르겠다...... restart어쩌고 저쩌고....

우리가 여기서 기대하는 것은 어떻게하면 Page Fault를 최소화할 수 있는가?

이것이 Demand Paging에서 고민해봐야할 이슈가 됨!

내용 정리

- 과거에는 프로그램이 수행이 될 때 프로그램의 코드나 데이터나 관련된 모든 메모리가 physical memory 안에 잡혀있어야 했음

- 이런식으로 수행을 시키면 메모리 값도 비싸고 프로그램 로켈러티 때문에 효율적이지 않음

- 비싼 램의 사이즈는 조금 가져가게 하고 대신 싼 디스크를 swap device로 사용하는 기법들이 생겼는데 그것이 virtual memory management

- virtual memory management는 logical address를 physical address로 매핑시켜주는 MMU라는 H/W 지원이 꼭 필요하다

- 요즘은 swap device를 사용할 수 없는 상황(과거상황)으로 돌아가는 경우가 있음 언제? 스마트폰, 디지털TV 왜? 스마트폰 안에 디스크가 없기 때문

- swap을 하려면 flash memory에다가 해야함 왜냐하면 디스크 대신에 스마트폰에서는 secondly storage로 solid-state device 이기 때문이다.

- flash memory를 파일 만들듯이 구성을 해서 사용하는 거죠

그렇다면 flash memory에 swap하면 되지 않냐? 왜 안될까?

flash memory는 erasable ROM입니다. 종이에 썼다가 지우고를 반복하면 종이가 찢어지죠? 

erasable ROM 또한 지우고 쓰고를 반복하면 망가지게 됨

Flash Memory를 Swap Device로 사용하지 않는 이유

Flash Memory는 Erase 횟수가 제한이 있기 때문에 Swap Device로 사용할 경우 수명이 급격히 줄어들게 된다.

스마트폰의 수명만큼 Flash Memory가 버티지 못하는 경우가 있음

Swap 은 굉장히 빈번하게 썼다 지웠다를 반복하기 때문에

이제는 swap 없이 memory를 manage하는 것이 다시 중요해졌음

이런 것들을 low memory killer(LMK) 라고 함 

어떻게 하면 될까? 프로그램을 죽이기!!!

사용자는 핸드폰 전원을 끄지 않고 계속 사용하니 모든 physical memory에 앱이 차 있음

원치않은 앱들도 존재할 수 있으니 걔네들을 잘 인지해서 프로그램을 죽이는 것이 큰 이슈가 됨

H/W System의 변화에 따라서 OS이 대응해야 할 이슈들이 계속 변하고 있음

지금까지 Demand Paging의 필요성, 기본적인 동작방식을 설명했음

나머지는 조금더 detail하게 들어갈 예정

그렇지만 결국 우리가 원하는 것은 Page Fault weight를 감소시키는 그래서 swap device와 physical memory 사이의 메모리 transfer가 있더래도 보이지 않게 또는 최소화 시키게 하는 것이 목표가 됨

Demand Paging을 여러 관점으로 나눠볼 수 있음

1. 어떤 페이지를 언제 physical memory로 불러들일 것인지 (Page Selection Policy)

2. Page Frame이 부족해서 victim을 골라 swap device로 보내야 하는데 어떤 놈을 고를 것인지 (Page replacement Policy)

3. 페이지 교체를 할 때 어느 pool에서 고를 것인가? 전체 프로세스들 중에서 고를 것인지 아니면 특정 프로세스 중에서 고를 것인지 (Page replacement style)

4. Page allocation style 이라고 할 수 있음. page frame을 어떤 프로세스에게 할당할 때 어떻게 할당 할것인지 (Page placement style)

---

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

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