운영체제는 어디에??
우리가 process를 실행할때 운영체제가 정말 많은 일을 해준다. process는 page table이 있어서 address translation을 통해서 physical table에 접근한다는건 알고 있다. 그렇다면 운영체제는 도대체 어디에 있어서 운영체제가 실행되는걸까?
결과적으로 말하자면, address space를 할당받을때, process는 노란색 부분까지만 할당받고, 나머지 초록색 부분은 OS에게 할당된다. 즉,user program은 노란색 부분까지만 메모리를 할당받을 수 있다.
요즘 컴퓨터는 segmentation과 page를 같이 쓰고 있다.
평소 user mode에서는 segmentation을 노란색 부분 까지만 읽을 수 있게한다. 그래서 OS가 있는 메모리에 접근하려고 하면 segmentation fault가 일어난다. 만약에 Exception이 발생하면 segementation 허용범위를 OS메모리까지 확장시켜줘서 kernal모드로 진입할 수 있게 해주는 것이다.
정리하자면, OS에게 할당되어 있는 memory는 page table에 맵핑 되어 있어서 항상 쓸 수 있지만, 접근은 segmentation으로 관리해서, 평소에 접근하려고 하면 user mode일때는 segmentation fault가 일어나고, kernal mode에서는 segmentation이 확장되어서 접근할수 있게 된다.
demand paging의 효율이 떨어진다....??
cache가 효율적으로 돌기 위해서는 locality가 중요할 수 밖에 없다. 앞에 접근했던 부분을 또 접근할 가능성이 높아서 cache로 사용하게 되고, 이게 잘 맞아 떨어질때 효율성이 높아진다.
우리가 memory에서 locality가 높게 자주 사용되는 부분을 working set이라고 한다.
이제 본론으로 들어가면, demand paging이 효율적으로 작동하기 위해서는 working set이 main memory보다 작아야 한다. 왜냐하면 자주 사용하는 working set이 main memory보다 커버리면, disk를 계속 드나들어야 하기 때문에 오버헤드가 커진다.
예를들어보자. main memory에서 process A를 돌려보았다. working set이 memory보다 작아서 문제가 없었다. process B,C,D 사용하다가 E까지 사용했더니 A~E까지 working set이 잡아먹는 memory 용량이 main memory를 넘어가기 시작했다. 이제 page를 쓰려고 할때마다 계속 paging(memory에 있던 victim page를 disk에 내리고 사용하려는 page를 메모리에 load하는것)이 일어나게 되어서 성능이 급격하게 저하된다.(Thrashing)
옛날 컴퓨터를 사용하다가 보면 창을 여러개 띄웠을때, disk에서 드르륵드르륵 하는 소리를 들어본적이 있을 수도 있다.
창을 띄웠는데 왜 hard disk에서 소리가 나지라고 생각할 수 있는데, 바로 demand paging 때문에 disk에 계속 접근하기 때문이다.
이때, 창을 끄면, working set의 크기가 줄기 시작하면서 main memory 안에서 해결이 되기 때문에, 소리가 나지 않는다.
Prepaging
일반적인 demand paging에서 page를 disk에서 memory로 load할때 spatial locality에 의해 주변 page까지 미리 가져 오는것을 말한다.
prefetching 이라고도 불린다.
성능을 dramatic하게 높일 수 있다.
storage에게 4kB씩 3번 요청할것을 12KB를 한번에 요청한다면, 같은 시간동안 훨씬 빠르게 된다.
Buddy System Allocator
Logically contiguous는 LA에서 page끼리 인접해 있는것을 말하고, Physically contiguous는 PA에서 인접해 있는 것을 말한다.
paging이라는 것 자체가 대부분 Logically contiguous하다고 physically contiguous하지 않다. 여러 곳으로 흩어져 있다. 근데 physically contiguous
가 필요할때가 있다. GPU는 memory를 cache처럼 사용한다. 그리고 당장 필요없는 메모리를 main memory에 갖다 놓는다. demand paging과 비슷하다.
GPU에서 다른 CPU의 메모리에 접근하고 싶어서 1GB 만큼의 page를 요청했는데 page 하나의 크기가 4KB이다. 그러면 256K개의 page를 요청한 것이고, 이 요청을 하기위해서는 page의 위치가 적혀있는 table이 필요하다. 이 table 조차 너무 크다. 그래서 효율이 너무 안좋다. 때문에, 이런식으로 하지 않고, 애초에 GPU가 memory에게 page를 요청할때, PA 1000부터 ~ +100개 이런식으로 요청한다. 그러면 일일이 찾으러 가지 않아도 되고 효율이 엄청 좋아진다.
device들도 마찬가지이다. physically contiguous하게 page를 요청한다.
그런데 문제는 이렇게 했을때, exteranl fragmentation이 발생할 수 있다는 것이다.
Buddy System Allocator
운영체제에게 memory를 요청하는 process가 일반적인 paging을 사용했다면, 한 페이지씩 요청하고 반환하고를 했을텐데, physically contigous한 page를 요청해야 한다. 하지만 문제는 위에서 말했듯이, exteranl fragment가 발생할 수 있다. 그래서 생각해 낸것이, Buddy System Allocator에서는 page를 2^n개 만큼씩만 요청할 수 있다. 예를들어 8개가 필요하면 8개주고 9개가 필요하다면 16개를 줘야한다. internal fragment가 발생할 수는 있지만, 이렇게 하는게 더 낫다고 생각했다.
만약 process가 2^n개의 page를 OS에 요청하면, physical memory에 2^n개의 chunk가 있다면 그냥 주면되지만, 없다면, 2^(n+1)개를 두개로 쪼개서 이중 하나인 2^n개를 주게 된다.
예를들어, 2개의 consecutive page가 필요하다고 했을때, 2개짜리를 봤더니 없어서, 4개짜리를 찾고, 없어서 8개짜리 찾고 없어서 16개짜리 찾는다. 위 그림에서는 16개짜리 chunk밖에 없다. 이때 이걸 반으로 쪼개서 8개짜리 두개를 만들고, 또 그중 하나인 8개짜리를 반으로 쪼개고 4개짜리 두개를 만들고, 그중 하나인 4개짜리를 반으로 쪼개서 2개짜리 2개를 만들고, 그중 하나인 2개짜리를 할당해준다.
Buddy라는 것은 자신이 만들어질때 같이 쪼개진 똑같은 크기의 chunk를 말한다.
예를들어서 16->8*2가 되었을때, 8이 각각 A,B라고 한다면, A의 Buddy는 B가 되고 B의 buddy는 A가된다.
Buddy system allocator 반환
1. 나 자신인 2page짜리가 다쓰고 반환하려고 자신의 버디를 찾았다. 그런데 아직 사용중이므로 자기 자신만 반환했다.
2. 1짜리 노란색이 다쓰고 반환하려고 보니까 자신의 버디가 free 상태이다. 그러면 자신과 병합해서 2page로 만든다.
3. 자신의 buddy인 2page짜리가 이미 free이므로 또 병합해서 4page를 만든다.
