[OS / 운영체제] Virtual Memory, Virtual Address Space, Demand Paging, Copy-on-Write

Background

프로그램이 아주 많은 Instruction으로 구성되어 있는데 다 Load 하는 것이 필요한가?
실제 프로그램을 실행하면 모든 영역이 사용되는 것이 아니다. 예를 들어 Error handling code들은 error 발생 이전까지 사용되지 않는다. 필요한 부분만을 load 하자는 접근이 가능해진다.

 

Background

필요한 부분만을 load하면 여러가지 장점이 생긴다. 첫 번째로 상당히 큰 프로그램을 실행할 수 있다는 것이다. physical memory의 양이 반드시 필요한 부분만 올릴 수 있다면 실행할 수 있게 된다. 그 결과 동일한 크기의 메인 메모리를 갖고 있다고 하더라도 더 많은 프로그램을 실행할 수 있다. 다음으로 Swaping을 할 때 I/O Overhead가 크게 줄어든다는 것이다. 

 

Virtual Memory

Logical 메모리와 Physical 공간을 분리한다. Virtual memory라는 개념이 logical memory와 거의 비슷한 개념이다. 실제 시스템에 존재하는 Physical memory와의 mapping을 Page table에 의해서 이루어진다. Page라는 Technique과 비슷하다. 왼쪽의 virtual memory 공간은 logical address space라는 개념과 상응한다. 프로세스는 각자 자기 자신의 virtual address space를 가진다. Paging 과 다른 점은 Vitual Memory와 Physical Memory의 크기 차이이다. 일반적인 page에  logial address space가 physical address page보다 작다. 공유하면서 사용하기 때문에 각각의 프로세스가 갖는 메모리 공간은 Physical Memory 공간보다 작을 수 밖에 없었다. 하지만 Virtual의 경우는 Virtual Memory가 더 클 수도 있다. 오른쪽 원기둥은 Disk에 해당한다. Swaping 에 해당하는 그림이라고 할 수 있다. 당장 사용하지 않는 Content는 Disk로 Save를 해서 빈 공간에 원하는 프로세스한테 주는 방법이다. 실제 어떤 프로세스가 Virtual Memory의 Content를 요구했다고 하면 실제 Physical Memory에 가서 존재하는지 확인을 하게 된다. 만약 존재하면 바로 실행하면 되지만 없으면 Disk에 있는 내용을 Physical memory로 읽어오는 과정이 필요하다. Physical Memory는 궁극적으로 Cache의 역할을 한다고 할 수 있다. 필요한 만큼만 Physical Memory에 load해서 사용하게 된다. Disk의 경우 Physical Memory보다 크기 때문에 프로세스가 아주 넓은 Virtual Memory를 요구하더라도 Cover할 수 있는 잠재력이 있다. 현재 존재하지 않는 Content라고 하더라도 Disk에서 가져와서 사용할 수 있다는 것이다. Virtual Memory의 크기가 Physical Memory보다 클 수 있다는 것. 

 

Virtual Memory

모든 프로그램이 load 될 필요가 없게 만들어준다. physical address space보다 훨씬 큰 Address space를 제공할 수 있다. 동일한 Address space를 여러 프로세스가 공유할 수 있다는 것이다. Page table에 동일한 frame number를 넣어주면 share가 가능하다고 했었다. Paging이 원래 가지고 있었던 shared page라는 개념을 물려받아 사용할 수가 있다. Page를 share할 수 있기 때문에 Process Creation이 더 효율적이게 된다. 3장에서 fork로 새로운 프로세스를 만들때 Parent를 그대로 복제하는 것을 기억해보자. parent와 child가 같다고 하면 Parent의 content가 child에게 바로 공유될 수 있다는 점이 있다. 더 많은 프로그램이 concurrent하게 실행될 수 있다. swap을 할때 I/O Data의 양이 급격하게 감소하게 된다. Virtual Memory를 사용해서 일부만을 swap in swap out을 한다면 overhead는 많이 줄일 수 있게 된다.

 

Virtual Address Space

각 프로세스는 자기가 독립적인 메모리 공간을 사용한다는 착각 속에서 실행하게 된다. 그런 것을 Virtual Memory가 제공하기 떄문이다. 각 프로세스는 0부터 시작하는 연속적인 메모리 공간을 가지고 있다. 64bit로 표현할 수 있는  address space는 어마하게 크다. physical memory는 page frame이라는 단위로 구성된다. page로부터 내려오는 동일한 성질이라고 할 수 있다. MMU가 logical과 physical mapping을 담당한다. 무엇보다 Virtual Memory의 좋은 점은 Swapping, Address Translation을 Application이 전혀 신경쓰지 않아도 된다는 점이다. Virtual Address Space는 sparce할 수 있다는 것이다. Address Space의 최대 크기는 크지만 실제 사용되는 크기는 일부에 불과하다는 것이다. 어떤 프로그램이 4GB라고 하자. 실제로 그 프로그램은 500MB밖에 사용되지 않는다고 하자. 이와 같이 실제로 존재하지 않지만 Address Hole들이 많이 존재하고 이것은 Sparce라고 할 수 있다. 오른쪽 그림을 Virtual Address Space라고 하자. 맨 아래에 code가 저장되고  local variable이 저장되는 data와 function call이 이루어지는 stack의 공간이 있다. stack은 위에서 아래로 내려오면서 커지도록 되어있고 heap은 그 반대이다. 파란색 중간의 경우 function call과 dynamic allocation~~

 

 

Shared Library Using Virtual Memory

2개의 process가 각각의 Address Space를 가지고 있고 물론 이는 Virtual Address Space이다. Shared Page를 이용하면 Physical한 공간에는 Library가 하나밖에 없는데도 양쪽에 있는 Address space에 Mapping할 수 있다는 것이다. 

 

Implementation Techniques

Demand paging은 paging과 swapping을 결합한 방식이다. Demand Segmentation 방법은 Segmentation와 swapping을 결합한 방법이다

 

Demand Paging

paging + Swaping. 일반적인 Swapper가 Process단위로 수행하는 데 반해 Demand paging의 경우 Page의 단위로 Swap in과 Swap out을 진행한다. 모든 page를 load하는 것이 아니라 선택적인 Load를 하게 된다. Lazy Swapper라고 부른다. 꼭 필요한 만큼만 최소한으로 Swap을 하면서 I/O 연산을 줄이고 효율을 높였다는 긍정적인 의미이다. Swapping의 기본 단위가 Page이기 때문에 pager라고 부르기도 한다. 

 

 

Demand Paging

요구되는 page만 로드하는 것이 핵심 아이디어. hardware의 Support가 필요하다. 프로세스가 하나 있고 이는 logical memory를 가지고 있다. 이는 궁극적으로 Disk에 존재하고 있는데 당장 필요한 Page를 Load한다는 것이다. 일부는 Memory에 존재하고 일부는 memory에 없는 경우가 있다. 그래서 Memory에 있는지 Disk에 있는지를 확인해야 하므로 HardWare의 Support가 필요하다. 이를 위해 Valid- invalid table을 이용한다.

 

page Table with Valid/inValid Bit

Page Table의 각 Entry마다 해당하는 bit가 있다. 2가지 조건을 만족하는 경우에만 한한다. page 자체가 적절한 Address여야 한다는 것. Virtual Memory에서는 각 Process에게 아주 넓은 Virtual Address Space를 제공한다. 하지만 sparce한 경우가 존재한다. 올바른 영역에 존재하지 않다면 그 자체로 invalid하다는 것이 된다. Page의 Content가 Physical Memory에 load되어 있어서 당장 사용할 수 있는 상태여야 한다는 것. Valid라는 것의 의미는 Page가 실제 존재하고 Load가 되어 있어야 한다는 And 조건을 의미한다. inValid는 두 조건 중 적어도 하나가 만족되지 않는 경우를 의미한다. Page-fault Trap이 발생했을 때 적절히 처리할 수 있는 Hardware support가 필요하다는 것이다. 프로세스가 특정한 위치를 Access하려고 하는데 i여서 실제 Access할 수 없는 상황의 경우를 의미한다. Page - fault가 발생하면 OS가 일을 해야 한다. 무엇인가 처리를 해줘야 한다. 그 과정은 Page Fault Handler라고 부른다.

 

Basic Concepts

Valid inValid bit이 i 값을 갖게 된다. 하나는 page 자체가 잘못되었거나 page는 존재하지만 Load되지 않았다고 해석할 수 있다. 제일 먼저해야 하는 것은 두 가지 중 어디에 속하는 지 를 판단해야 한다. page Table은 Page의 Content가 어디에 존재하는지 알려주는 table을 가지고 있다. Disk에 있으면 Disk의 Block 번호 또는 File의 번호를 가지고 있다. 그 표를 해당하면 Page가 실제로 존재하는 것인지를 확인할 수 있다. 즉, 존재하지 않는 page를 Access하려고 했었다면 이것은 잘못된 것이다. Bug나 Hacking 시도로 해석할 수 있다. 두 가지 모두 다른 시스템한테 악영향을 미치지 않게 강제 종료를 시키게 된다. Page는 존재하는 페이지 이지만 아직 load되지 않은 경우, Load를 하기 위해서 빈 공간이 필요하다. 요청된 page를 table을  update해야 한다. 해당 page의 valid의 값을 V로 바꿔주고 조금 전에 load된 frame number를 page table에 넣어줘야 한다는 것.

 

Handling Page-Fault

특정한 메모리 영역을 Access한다. 주소를 생성하고 그 주소는 Virtual address가 된다. page number를 가져다가 page table에 접근을 한다. 그 위치로 가서 제일 먼저 valid in valid를 체크하고 invalid의 경우 trap이 발생한e다. Interrupt Handler가 page Fault를 인지하고 Page Fault Handler를 작동한다. 만약 disk에 존재한다면 Disk에 가서 Memory로 swap하게 된다. 올리게 되면 Valid bit를 바꾸게 되고 원래 실행하려고 했던 Instruction 부터 시작하게 된다.

 

Basic Concepts
Page fault가 발생하면 Performance가 down된다는 것을 알 수 있다. 그 순간 잠깐 멈추고 Disk로 이동을 하게 되고 Page를 update하기 까지 여러 Handler와 Disk  Access를 해야 한다. 실행 속도가 급격하게 저하된다. 얼마나 자주 Page Fault가 발생하는가? 이론적으로 page fault가 엄청나게 많이 발생할 수 있다. Instruction 자체가 한 페이지에 존재하고 값을 읽어오는 page와 값을 쓰려는Page가 있을 것이다. Instruction 하나가 3개의 page fault를 발생시키는 경우도 발생할 수 있다. 메모리의 특정 위치를 Access를 했다면 다음 Memory 위치는 그 주변일 가능성이 높다. H/W Support는 page table에서 valid-invalid bit 제공이고, Disk처럼 Virtual Memory의 Content를 저장할 수 있는 Swap space가 필요하다. 

 

Performance of Demand paging
프로그램이 메모리를 Access하면서 실행하는 시간을 다음과 같이 나타낼 수 있다. ma는 main Memory의 접근 시간이다. 
p는 page fault의 확률이다. 

 

Performance of Demand Paging
메모리 Access time을 200 nano라고 가정하고 page fault를 8 msec이라고 하자. page fault가 나타났을 때는 없을 때보다 40배 정도 커지게 된다.

 

Execution of Program in File System
File을 복사하는 Overhead가 발생한다. swap space는 main memory의 content를 대피하기 위한 공간이다. File system에 있는 실행파일 자체를 Content로 보고 page와 바로 mapping 시키는 것. 메모리 공간의 page와 file system의 실행파일하고 mapping을 시켜버린다. 그리고 demand paging을 가동하면 page fault가 발생하고, 실행파일을 해당 블럭에서 읽어오고 실행하게 된다. 2 번째 option의 성능이 더 빠르다.! 

 

Copy-on-Write
Process를 Create할 때 성능 개션을 하게 해준다. fork를 호출하면 parent를 복사해서 child를 만들어내게 된다. 그 순간 child의 형태는 parent와 동일하게 된다. 물리적으로 봤을 때 실제 메모리 content를 복사할 필요가 없어진다. Creation Time이 짧아진다. 복사할 필요없이 Sharing하기 때문이다. 아주 빠르게 진행할 수 있게 된다. Process가 새로 만들어지면 독립성을 가질 수 있어야 한다. 한 프로세스의 메모리는 다른 프로세스가 공유될 수 없는 독립적이어야 함을 배웠다. 논리적인 상황에서는 분리되어 있지만 물리적인 상황에서는 공유되어 있다. 

 

Copy-on-Write
논리적인 메모리 Content가 일치한다. Physical하게 공유하는 방법은 frame number를 동일하게 해주는 것이다. parent에 page C에 write한다고 해보자. 그 페이지에 해당하는 내용이 CHild에게 영향을 줘서는 안된다. 왜냐하면 독립적인 Process이기 때문이다. 이 상황의 경우 완전히 다른 메모리 Frame이 된다. Physical Memory안에서 Copy하는 양을 최소화할 수 있게 해준다.