Resident Set Size
Resident Set Size는 프로세스마다 어떻게 할당할지 page replacement 하기 전에 정해줘야 한다.
Resident Set Size를 결정하는 방법에는 두 가지 방법이 있다.
- Fixed-allocation
- Variable-allocation
Fixed-allocation
각 프로세스마다 일정한 개수의 페이지 프레임을 나누어 주는 것이다.
Page Fault 가 발생하면, 그 안에서 나누어준 페이지 프레임 안에서 교체할 페이지를 결정한다.
⇒ 각 프로세스에 할당된 페이지 프레임 수에 변화 X
Variable-allocation
프로세스마다 할당된 페이지 프레임 수에 변화 O
→ 할당되는 프레임 수가 늘어났다 줄어들었다 한다.
프로세스가 실행을 시작해서 끝날때까지 계속해서 할당하는 프레임 수가 늘어났다 줄어들었다 한다.
Fixed-allocation 보다 간단하다.
Resident Set Size 를 결정하는 방법에는 세가지 방법으로 구현할 수 있다.
Local Scope
나한테 할당된 페이지 프레임 중 버리는 페이지를 선택한다.
내 페이지를 버리고 내 페이지를 가져온다. 프레임 숫자에 변화가 없다.
Global Scope
존재하는 전체 페이지 프레임 중 버리는 페이지를 선택한다.
⇒ 따라서 어떤 프로세스는 할당되는 페이지 프레임 수가 증가하고 어떤 프로세스는 할당되는 페이지 프레임 수가 감소할 수 있다.
Fixed Allocation, Local Scope
프로세스에게 정해진 갯수만큼 페이지 프레임을 할당한다.
- Fixed Allocation에 Global Scope 는 존재하지 않는다.
- Resident set 의 크기는 고정되어 있다.
- Page Fault 가 발생하면, 내게 할당된 페이지 프레임의 페이지 중 하나를 선택해 버리고 새로운 것을 가져온다.
장점
LRU 방식을 사용할 수 있다.
Local Scope 로 교체되므로 Page Fault 숫자 기준으로 LRU 방식이 가장 효율적이다. LRU 는 공간적 overhead 와 특히 시간적 overhead 가 존재하므로 Global scope 에서는 사용될 수 없다.
→ 메모리 안의 전체, 모든 페이지가 가장 최근에 언제 사용됐는지 비교할 수가 없기 때문이다.
하지만, Local Scope 의 경우 나에게 할당된 페이지 수가 얼마 안되기 때문에 LRU 가 가능하다.
단점
얼만큼 할당할 지 정하기 어렵다.
- Frame 크기가 너무 클 경우 → 공간 낭비가 크다.
⇒ 많은 프로그램이 메모리에 존재하지 못한다. (나는 2개 프레임만 있으면 되는데 5개 할당해주면 3개는 비어있는 공간이 된다.) - Frame 크기가 너무 작을 경우 → Page Fault 수가 증가한다.
- Decide ahead of time the amount of allocation to give a process
- If allocation is too small, there will be a high page fault rate
- If allocation is too large there will be too few programs in main memory
Variable Allocation, Global Scope
- Clock 기법을 사용한다.
- 메모리 안에 있는 프레임을 Circular Buffer 처럼 생각을 한다.
- Page Fault 가 자주 발생 O 프로세스 → 페이지 프레임 할당 증가 ↑
- Page Fault 가 자주 발생 X 프로세스 → 페이지 프레임 할당 감소 ↓
- 할당된 메모리가 가득차면 기존의 것을 버리는데, Global Scope 를 이용하므로 전체 메모리의 페이지들 중에서 버릴 페이지를 선택한다.
⇒ 어떤 Process 는 새로운 페이지가 들어와서 프레임수가 증가하게된다.
⇒ 어떤 Process 는 페이지가 버려져서 프레임수가 감소하게 된다. - 많은 OS 시스템에서 선택하는 방법이다. Fixed Allocation 보다 Variable Allocation 이 좋다.
- Easiest to implement; Adopted by many operating systems
- Operating system keeps list of free frames
- Free frame is added to resident set of process when
a page fault occurs - If no free frame, replaces one from another process
- x 축 = 시간
- y 축 = wokring set size
working set
이 프로세스가 작업을 하는데 필요한 페이지 수
페이지 프레임에 제한 없이 이 프로세스가 원하는대로 페이지 프레임을 할당해주고 실제로 페이지를 얼만큼 사용하는지 확인하면,
처음에 프로세스가 실행을 하면 필요한 페이지 수가 증가해 새로운 페이지가 메모리가 막 들어온다. 어느정도 페이지가 들어오면, 더 이상 페이지가 안들어오고 그 상태로 계속 실행을 한다.
따라서 계속 일정한 working set 을 유지하다가 갑자기 어느 순간 다른 페이지들을 호출하면 다시 페이지 크기가 늘어난다.
working set 이 늘어 났다 줄어드는 것 처럼 보이는 이유는 기존의 있던 페이지들과 새로 들어온 페이지들이 합쳐져서 늘어나는 것처럼 보였지만 기존의 있던 페이지는 사용하지 않기 때문에 다시 working set 의 크기가 줄어든다.
어떤 프로세스도 처음 실행을 시작하면서 끝날때까지 필요한 페이지 수가 일정하지 않고 실행하며 계속 늘어났다 줄어들었다가를 반복 한다.
⇒ 새로운 페이지가 계속 필요하다.
페이지가 버려진 프로세스는 working set 이 줄어든다.
Page Fault 증가 → working set 이 증가하는 중
= 새로운 페이지가 계속 필요하다는 뜻
⇒ 따라서 더 많은 프레임 할당해서 필요한 working set 이 메모리 안에 들어올 수 있게 해준다.
이 과정에서 다른 프로세스의 페이지를 버린다. 아무거나 버리지 않고 use bit 가 0인 것을 버리므로 오랫동안 사용되지 않는 페이지를 버린다.
⇒ 즉, 페이지가 버려진 프로세스는 지금 working set 이 줄어드는 단계라는 것이다. 따라서 working set 이 줄어들어서 예전에 working set 이 컸을 때 가져왔던 페이지들이 이제 필요가 없어졌다는 뜻이다.
- working set 이 큰 경우 → 더 많은 페이지 프레임 할당
- working set 이 작은 경우 → 더 적은 페이지 프레임 할당
궁극적으로 working set == resident set 이 되면, 페이지 fault 가 일어나지 않는 것이다.
내가 필요한 만큼 다 메모리에 들어와 있으면 page fault 가 일어나지 않는다.
variable allocation 의 global scope 는 page fault 수를 줄이는데 가장 적합한 방식이다.
Fixed Allocation 는 page fault 가 일어나도 프레임을 더 할당해주지 않기 때문에 결국 working set이 전부 메모리에 들어올 수 없다.
→ 어떨때는 너무 부족하고 어떨때는 너무 널널하다.
variable allocation 의 global scope 의 가장 적합한 page replacement 는 clock 기법이다.
global scope 에서는 전체 시간을 비교할 수 없기 때문에 LRU 를 사용할 수 없다.
Variable Allocation, Local Scope
- 새로운 프로세스가 시작하면 기본적인 수의 정해진 페이지 프레임이 할당된다.
→ 프로세스 타입, 프로그램 요청, ...에 따라 - 프로세스가 실행하며 page fault 가 발생하면 Local Scope 를 사용하므로 자신의 프레임 안에서만 페이지를 교체한다.
⇒ 페이지 프레임 크기가 고정된다. 하지만, 내가 훨씬 더 많은 페이지가 필요하면, working set 이 늘어나는 중이면, page fault 가 계속 발생할 것이다. - 프로세스의 page fault 수를 계속 검사하며 page fault 수에 따라 resident set 의 크기를 조절한다.
- page fault 가 너무 클 경우 → resident set 의 크기를 늘려준다.
- page fault 가 너무 작을 경우 → resident set 의 크기를 줄여준다.
장점
- LRU 와 같은 기법을 적용할 수 있다.
- Variable Allocation 이라 Page Fault 수를 계산해서 주기적으로 나에게 할당된 resident set 크기를 조절해줄 것이기 때문에 working set 이 커지면 처음에는 Page Fault 가 많이 발생하겠지만, 더 많은 resident set 을 받게 될 것이다.
- When new process added, allocate number of page frames based on application type, program request, or other criteria
- When page fault occurs, select page from among the resident set of the process that suffers the fault
- Reevaluate allocation from time to time
UNIX Memory Management
대부분의 OS 시스템에서 메모리를 관리할 떄 대부분 Paging 기법과 Virtual memory system 을 사용하고 모두 페이지 테이블과 TLB 를 이용해서 동적으로 relocation 을 진행한다.
단, 페이지 크기와 페이지 replacement 하는 알고리즘은 시스템 마다 조금씩 다르다.
Unix 는 두 가지 메모리 management 기법이 있다.
일반적인 user processes
- 페이지 기반의 virtual memory system 을 사용한다.
- 페이지 기반의 relocation 을 한다.
- TLB 도 사용한다.
Kernel을 위한 memory 할당
Dynamic Partitioning 을 사용한다.
buddy system 의 변형된 형태를 사용한다.
Two Memory Management Mechanism
- For processes : Page-based Virtual Memory System
Page Table based Dynamic Address Translation (w/ TLB) - Kernel memory allocator : Dynamic Partitioning (변형된 형태의 buddy system)
UNIX Memory Management(2)
Two-Handed Clock Page Replacement Algorithm
- Variable allocation Global Scope 사용
- 바늘이 한 개일 경우, 시간이 오래걸릴 수 있다.
↳Clock기법의 문제점: 굉장히 오랫동안 페이지 교체를 하지 않은 경우, 모든 use bit 가 다 1이 될 것이다. 이후, 페이지를 교체해야할 할 때, 바늘이 움직이면서 전체 페이지 프레임들을 훑어봐야 하기 때문에 시간이 굉장히 오래걸린다. - 2번의 문제점을 해결하기 위해, Unix 에서는 바늘을 2개 설정한다.
페이지 교체가 필요한 시점에 바로 페이지를 교체할 수 있도록 한다.
→free frame최대한 확보 할 수 있도록 설계한다.
Reference Bit (=Use Bit)
- 사용 O → 1
- 사용 X → 0
Fronthand (첫번째 바늘)
Reset the Referece Bit to 0
- 쭉 움직여 가면서 Referece Bit 를 0 으로 만든다.
- 페이지 교체를 할 때만 바늘이 움직이는게 아니라 계속 움직인다.
↳ 앞에서 얘기했던Clock기법에서는 페이지 교체를 할 때 바늘이 움직였지만, UNIX 에서는 평상시에 계속 바늘이 움직이며 Referece Bit 를 0 으로 만든다.
만약, 바늘이 한바퀴 다 도는데 한시간이 걸린다고 가정하면,
지금 시스템 상의 어떤 프레임의 use bit 가 1이라고 하면
→ 최근 한시간 이내에 사용이 되었다는 뜻이다.
use bit가 0이라는 뜻은 1시간동안 사용되지 않았다는 뜻이다.따라서 바늘이 움직이는 속도를 당연히 OS 가 조절한다.
use bit 가 최근시간 T 동안 사용이 된 페이지와 사용이 되지 않은 페이지를 구분할 수 있게 한다.
Backhand
Pages w/ Reference Bit 0 into Paged-Out List
쭉 움직이면서 reference bit 가 0인 페이지들(상당한 기간동안 사용되지 않은 페이지)을 Paged Out List 에 모아둔다.
Paged Out List
버릴 페이지들을 모아둔 곳
페이지를 버릴 때 중요한 것은 이 페이지의 modify bit 가 1인지 0인지에 따라서 작업 내용이 달라진다.
- modify bit = 0 → 하드디스크에서 메모리로 올라와서 변경된 사항이 없다.
⇒ 그냥 버리면 됨 - modify bit = 1 → 하드디스크에서 메모리로 올라와서 변경된 사항이 있다.
⇒ 그냥 버리면 안되고 하드디스크에 다시 쓰고 버려야 한다.
⇒ 즉, 하드디스크에 써야만 버린 페이지가 된다.
이러한 페이지들을 쭉 모아둔 다음 이 중에 modify bit 가 1인 애들을 어느정도 Paged Out List 길이가 가 길어지면 하드디스크로 다 쓴다.
↳ 다 쓰고 나면 Paged Out List 에 있는 페이지들은 사실상 Free Frame 과 동일하다. 빈 공간과 똑같아 지는 것이다.
⇒ 평상시에 Free Frame 을 만들어 놓는 작업
하드디스크로 접근 할때는 접근할 때 가져가는 양보다 접근 횟수가 실행 속도에 영향을 많이 끼친다.
⇒ 모았다가 한꺼번에 버리는게 굉장히 중요하다.
⇒ 평상시에 free frame 을 만들어 확보해 놨다가 교체 할 때의 시간을 줄인다.
"Two Handed" Clock Page Replacement
두 바늘이 움직이는 속도가 중요하다.
Fronthand 의 속도 < Backhand 의 속도
use bit 가 모두 0 이 된다. reference 해서 1로 바뀔 시간 X ⇒ Paged out list 가 길어진다.
Fronthand 의 속도 > Backhand 의 속도
모두 reference 되어서 use bit 가 모두 1 이 된다.
⇒ 두번째 바늘이 Paged out list 에 집어 넣을 페이지가 없다.
두 바늘이 너무 붙어있으면
Paged out list가 길어지고, 두 바늘이 너무 떨어지면Paged out list가 짧아진다.
⇒ 속도 조절을 해야한다.
OS
- OS 는
Paged out list의 길이를 보면서 두 바늘의 속도를 조절한다. - OS 의 목적: Free Frame 을 가장 적절한 수만큼 관리하는 것
ex) → 나는 항상 10개정도는 프레임을 빈 공간으로 가지고 있으면 좋겠다.항상 일정한 개수의 Free Frame 확보하고, 페이지 교체가 필요한 시점에는 별도의 overhead 없이 바로 페이지 교체하도록 하는게 "Two Handed" Clock Page Replacement
→ Paged out list에 넣어 놨다가 다시 필요해지는 경우도 있으므로 그냥 Paged out list 에서 빼면 된다. 다시 하드디스크에서 페이지로 가져올 필요가 없다.
→ 여기서 버려짐 ⇒ 진짜 사용하지 않는 페이지를 버린다는 의미
Windows Memory Management
- Page-based Virtual Memory System 사용
- Windows uses variable allocation, local scope
→ 주기적으로 다시 Page Fault 수를 계산해서 Page Frame 을 변경한다.- Page Fault ↑ → Resident set 크기 ↑
- Page Fault ↓ → Resident set 크기 ↓
- ⇒ Working-Set == Residet set 이 되도록 설정한다.
- Working-Set based Memory Management
Working-Set 과 Resident-Set 은 비례관계이다.
⇒ local scope 을 사용하므로 LRU 사용 가능
→ 할당된 프레임이 적기 때문에 사용가능 (시간적 overhead 거의 없음)- When main memory is plentiful, the resident sets of
active processes grow. - When memory becomes scarce, less recently used pages are out.
- When main memory is plentiful, the resident sets of
- Less recently used pages out
