- 캐슁은 한정된 빠른 공간(=캐쉬)에 요청된 데이터를 저장해 놓으면 다음에 똑같은 데이터 요청이 오면 캐쉬로부터 서비스를 하는 것이다. 페이징 기법 뿐만 아닌 여러가지 컴퓨터 시스템 환경에서 사용된다.
- 캐쉬는 캐쉬 안의 데이터중 어떤 것을 쫓아낼지를 결정하는 알고리즘에 있어 시간 제약 조건이 있다. 이 결정 시간에서 일정 시간을 넘어서는 안되는 것이다. 이 시간은 O(1)에서 O(logN)까지만 허용된다.
- 페이징 시스템에서는 제약조건이 더 많다.
- 페이징 시스템에서 LRU나 LFU를 사용할 수 있을까? 프로세스 a가 cpu를 잡고 수행중일 경우 프로세스 a의 논리적 메모리에서 매 순간 지시를 하나씩 읽어와 실행할 것이다.
- cpu에서 프로세스a에 대한 논리 주소를 주면 페이지 테이블을 통해 물리적 메모리의 내용을 cpu로 읽어들여야 할 것이다.
- 그러나 만약 주소 변환시 해당 페이지가 이미 물리적 메모리에 올라와 있을 경우, 물리적 메모리에서 직접 내용을 읽어 가져간다. 이 과정에서 운영체제는 하는 일이 없다. 하드웨어적으로만 주소 변환이 일어나기 때문이다.
- 반면 주소변환 시도를 했는데 invalid라 페이지 폴트가 발생하면 디스크 접근 즉 i/o가 필요하므로 trap이 발생해 cpu가 운영체제로 넘어가 운영체제가 페이지 폴트가 난 페이지를 읽어 디스크에 올린다. 그 중 기존 페이지 하나는 쫓아내는 replacement를 해야 한다.
- 그러나 어떤 것을 쫓아낼지 결정할 때 LRU를 사용하면 참조가 오래된 페이지를 쫓아내야 하는데, 과연 운영체제가 참조가 오래된 페이지를 알 수 있는가? LFU의 경우에도 마찬가지로 참조횟수가 적은 페이지를 알수 있는가?
- 답은 "알 수 없다" 이다. 페이지 폴트가 발생하기 이전 과정에서, 요청한 페이지가 이미 메모리에 올라와 있으면 운영체제에게 cpu가 넘어가지 않는다고 했다. 즉 운영체제는 이전 페이지의 참조 시간, 혹은 참조 횟수에 대한 정보를 전혀 모르는 것이다. 페이지 폴트가 나야만 현재 페이지가 메모리에 올라오는 정보만 알 수 있다.
- 그럼 페이징 시스템은 replacement를 위해 어떤 알고리즘을 사용할 수 있을까
- 그래서 사용되는 알고리즘이 바로 "클락 알고리즘이다". 최근에 사용되지 않은 페이지를 쫓아내는 방식이다. LRU와 비슷한 알고리즘으로 세컨 찬스 알고리즘, NRU(not recently used)이라고도 불린다. 마치 시계방향처럼 움직이는 알고리즘이라 하여 클락 알고리즘이라 불린다.
- 위 각각의 사각형이 페이지 프레임이다. 물리적 메모리 안의 페이지를 의미한다. 어떤 페이지가 참조되어 cpu가 그것을 사용하면 페이지에 refrence bit이라는게 붙어있다. 이는 주소변환을 하는 하드웨어가 페이지를 참조할 때 레퍼런스 비트를 1로 세팅해 페이지가 참조됐다는 것을 표시하기 위한 것이다. 이는 운영체제가 아닌 하드웨어가 하는 일이다.
- 만약 페이지 폴트가 나서 운영체제가 어떤 페이지를 쫓아내려 할 때는 레퍼런스 비트를 참조하여 이것이 1이면 페이지가 최근에 참조됐다는 것을 알 수 있다. 왜냐면 운영체제가 어떤 페이지를 쫓아낼 지 결정하기 위해서 레퍼런스 비트를 한 번 참조할 때마다 그 비트가 1이면 0으로 바꾸고, 쫓아내지 않고 다른 페이지를 참조한다. 만약 계속 참조하다가 레퍼런스 비트가 0이면 그 페이지를 쫓아낸다.
- 위의 시계바늘은 운영체제가 현재 참조하는 페이지의 레퍼런스 비트를 확인하는 것을 의미한다. 즉 레퍼런스 비트가 0이라는 뜻은 시계바늘이 한 바퀴 돌 동안 그 페이지에 대한 참조가 없었다는 뜻이다. 1이라는 뜻은 시계바늘이 한 바퀴 돌 동안 적어도 한 번의 참조가 있었다는 뜻이다. 즉 하드웨어가 페이지를 참조할 때 레퍼런스 비트를 1로 바꾸고, 운영체제는 페이지의 레퍼런스 비트를 차례로 읽으며 1을 0으로 바꾸고 0인 페이지는 쫓아내는 것이다.
- 추가적으로 modified 비트를 하나 더 두는데, 이는 어떤 페이지가 참조될 때 read로 참조될 수도, write로 참조될 수가 있는데, write로 참조되면, 즉 i/o를 동반하면 이 비트를 1로 세팅한다. 이는 어떤 페이지가 레퍼런스 비트가 0 이라 쫓아낼 때 modified 비트가 0이면, 그 페이지는 백킹 스토어가 물리적 메모리로 올라온 이후로 write 즉 변경이 발생하지 않은 것이므로 그냥 지워버리면 된다.. 즉 백킹 스토어에 있는 copy가 그 페이지와 완전히 동일한 내용이라는 것이다. 반면 modified 비트가 1이면 페이지가 메모리에 올라온 후 내용이 수정된 것이므로, 그냥 지우는 것이 아닌 백킹 스토어에 변경된 내용을 반영한 후 지워야 한다.
- 따라서 modified 비트가 1이면 추가로 할 일이 드므로 가능하면 modified 비트가 0인 것을 쫓아낸다.
- 페이지 프레임의 할당에 대해 설명하겠다.
- 만약 지시를 수행하기 위해 어떤 루프를 돌고 있을때 그 루프를 구성하는 페이지가 3개가 있다. 그럼 프로그램에 3개의 페이지를 주면 프로그램을 반복하는 동안 페이지 폴트가 나지 않는다. 덜 주면 페이지 폴트가 계속 난다. 또 메모리 참조 명령어 수행시 최소 할당되어야 하는 페이지 프레임 수가 있다.
- 따라서 각 프로세스에 얼마만큼의 페이지 프레임을 할당할 것인지를 결정하는 것이 중요하다.
- 할당은 세 가지의 방법이 있다.
- 첫째로 Equal allocation 모든 프로세스에 동일한 갯수의 페이지를 할당한다. 그러나 프로그램마다 필요한 페이지가 다르므로 비효율적이다.
- 따라서 Proportional allocation, 즉 프로세스 크기에 비례해 할당할 수 있다. 그러나 같은 프로그램도 시점에 따라 필요한 페이지가 다를수 있다.
- 따라서 Priority allocation이라 하여 프로세스의 cpu 우선순위에 따라 다르게 할당할 수 있다.
- global replacement는 미리 할당을 하고 고정하는 것이 아닌, 예를 들어 어떤 시점에서 어떤 프로그램이 페이지가 많이 필요로 하면 다른 프로그램의 페이지를 빼앗아 할당해주는 replace를 해주는 것이다. 이 경우 FIFO,LRU,LFU를 사용할 수 있다. 워킹셋, PFF 알고리즘을 사용한다.
- 반대로 Local Replacement는 앞의 방법처럼 프로그램에 미리 메모리 할당을 하고, 만약 한 프로그램 내에서 새로운 페이지가 필요하면 무언가를 쫓아내고 프로그램(프로세스) 별로 FIFO,LRU,LFU 등을 사용할 수 있다. global의 경우 다른 프로세스의 페이지를 쫓아내 가져올 수 있지만 local의 경우 자신에게 할당된 페이지만 쫓아낼 수 있고, 다른 프로세스의 페이지는 건드릴 수 없다.
- 쓰레싱은 어떤 프로세스에 페이지가 너무 적게 할당되 페이지 폴트가 너무 많이 일어나는 상황이다.
- 위 그림은 어느 시점 까지는 메모리에 올라가는 프로그램이 늘어남에 따라 cpu 이용률이 올라가는 모습을 보여준다. 이게 일반적인 모습이다.
- 그러나 어느 지점에서 이용률이 떨어지는데 쓰레싱이 발생한 것이다. 프로세스에게 페이지가 너무 적게 할당되어 페이지 폴트가 발생하고, cpu가 지시를 수행하려는데 요청한 페이지가 메모리에 없어 i/o를 계속 하러가야 한다.
- 그런데 운영체제가 cpu 이용률이 낮으면 cpu가 논다고 잘못 판단하여 프로그램(프로세스)을 더 늘린다. 그럼 각 프로세스의 메모리 용량이 더 적어지고 페이지 폴트가 계속 발생한다. throughput이 낮아진다.
- 이를 막기 위해 동시에 메모리에 올라가는 프로세스 수를 조절해야 한다. 이를 해주는 알고리즘이 워킹셋과 PFF 알고리즘이다.
- 프로세스가 특정 시간에는 특정 메모리 위치만 집중적으로 참조하는 것을 locality라 한다. 집중적으로 참조되는 페이지의 집합을 locality set이라 한다.
- 워킹셋 알고리즘에서는 locality set을 워킹셋이라 부른다.
- 워킹셋에 포함된 페이지는 적어도 메모리에 한꺼번에 올라오도록 보장해야지만 페이지 폴트가 잘 나지 않는다.
- 그러나 메모리에 너무 프로그램이 많으면 워킹셋이 보장이 안된다. 이 경우 모든 페이지를 통째로 반납하고 프로세스가 디스크고 스왑아웃 된다. (suspend)
- 이런 식으로 워킹셋이 한꺼번에 메모리에 올라가는게 보장되지 않으면 suspend 시켜 스레싱을 방지한다.
- 워킹셋은 미리 알 수 없으므로 과거를 통해 워킹셋을 추정하여, 과거 델타시간 동안 참조된 페이지를 워킹셋으로 간주하여 메모리에서 쫓지 않고 유지한다.
- 델타 시간을 윈도우라고 부른다.
- 밑의 그림에서 윈도우는 10으로, 과거 10만큼 참조된 페이지(1,2,5,6,7)를 워킹셋으로 하는 것이다. 따라서 그 시점에 프로그램에 5개 페이지를 할당할 수 있어야 한다.
- 워킹셋 크기는 계속 바뀐다. 옆에서는 워킹셋이 (3,4)이다. 이 시점에는 두개 페이지를 할당할 수 있어야 한다.
- 참조된 페이지를 델타시간 유지한 후 버린다.
- 워킹셋이 보장 안되면 그 프로그램을 스왑 아웃 시킨다.
- PFF 역시 프로세스 수를 조절하여 스레싱을 방지하는 것이다. 그러나 워킹셋처럼 추정하는 것이 아닌 직접 특정 시간과 특정 프로그램의 page falut rate를 보는 것이다. 따라서 페이지 폴트를 많이 일으키는 프로세스에 페이지를 많이 준다.
- 그래프에서 어느 정도의 페이지 폴트 발생율(upper bound)를 넘으면 페이지를 할당시켜 낮추고, 반대로 페이지 폴트가 너무 발생 안하면 쓸데없이 메모리가 많은 것이므로 페이지를 빼앗아 발생율을 조금 높인다.
- 만약 어떤 프로세스에 더 줄 페이지가 없는 경우 그 프로세스를 통째로 스왑 아웃 시켜 스레싱을 방지한다.
- 그런데 페이지의 사이즈는 어떻게 결정할까? 보통 32비트 주소체계에서 4kb를 쓰는데 64비트로 바뀌면 페이지 사이즈가 커질 필요성이 있다. 따라서 메모리 크기가 커지면 페이지 크기를 키운다.
- 페이지 사이즈를 감소시키면 페이지 수가 증가하고, 페이지 테이블 엔트리 수가 더 많이 필요하므로 페이지 테이블을 위한 메모리 낭비가 심해진다. 반면 페이지 안에서 사용되지 않는 부분이 줄어들어 효율성이 높아질 수 있다. 페이지가 너무 크면 페이지가 조금 필요해도 필요 없는 부분까지 메모리에 올라올 수도 있다.
- 반대로 locality 활용 측면에서 는 페이지 사이즈가 큰 것이 좋다. 어떤 함수가 실행되면 그 함수 구성 코드들이 연달아 순차적으로 참조되기 때문에 페이지 폴트가 났을때 큰 페이지 하나를 올리면 처음에는 페이지 폴트가 나도 그 다음에는 메모리에 올라온 이후로 페이지 폴트 없이 참조될 수 있기 때문이다.
- 또한 disk transfer의 효울성도 페이지가 클수록 좋다. 디스크는 기본적으로 seek로 디스크가 회전하며 특정 위치에 가서 내용을 읽는데 이 시간이 오래 걸리므로 가능하면 한번 읽을때 많이 읽는게 좋기 때문이다.
- 따라서 최근에는 페이지 크기를 점점 키우는 추세다.
하마드