이 포스팅에서는 Varaible allocation(VA) based 교체 기법 중 WS 기법을 정리했다.
VA based memory management
- VMIN(Variable MIN) algorithm
- WS(Working Set) algorithm
- PFF(Page Fault Frequency) algorithm
Working Set 메모리 관리기법
working set: 어떤 프로그램이 특정 시간에 집중적으로 접근하는 page들의 set.
수학적으로 정의하면, 현재 시점 t에서 window sizeΔ 전만큼의 시간동안 접근된 pages들의 set이다.
-
Working set memory management
-
Based on locality
-
항상 그 프로세스의 working set을 메모리에 유지시키는 기법 -> reduce page fault rate, improve system performance.
-
window size의 크기가 성능에 큰 영향을 미친다.
loop별로 working set이 다른데, 각각 page 개수가 다르기 떄문에 메모리가 가변적으로 할당되는 VA기법임을 확인할 수 있다.
곡선 구간이 working set이 바뀌는 구간으로 transition구간이다. page fault가 발생하는 transition구간은 매우 짧게 지나간다.
초기에 0,3,4 page가 있다고 가정한 WS기법의 예시이다. time2일때, page4는 Δ=3가 지났기떄문에 나간다. 마지막 행을 보면 number of frames allocated가 계속 변하는 것을 볼 수 있다.Δ를 통해서 최근에 참조되지 않은 page는 나가도록 하기 때문에, locality에 기반한 LRU와 비슷한 기법이라고 볼 수 있다. 차이점은 LRU는 VA이기 때문에 메모리할당량을 고정시켜서 그 만큼만 메모리 안에 유지하고, WS는 시간을 제한해서 그 시간동안에만 메모리 안에 page를 유지한다.
-
-
Performance
- During time interval [1,10] : # of page faults = 5
- During time interval [1,10] : mean number of frames allocated = 3.2
- Analysis : 평균 3.7 page frame allocate 당 5번의 page fault
-
Characteristics
- page fault가 없고 들어오는 page가 없는데 나가는 page가 생김
- 들어오는 페이지가 있는데 나가는 page가 없을 수 있다.
-
단점
- Overhead : page fault 발생 여부와 상관없이 page reference를 계속 업데이트해줘야한다. -> (page fault 발생 시에만 update하는 기법이 PFF기법)
Other Considerations
앞서 살펴본 allocation 기법부터 교체기법 외에도 가상메모리 시스템에 영향을 미치는 세가지 요소가 더 있다.
Page size
- page size : 2^7 (128) Bytes ~ 2^22 (4M) Bytes -> 보통 4KB
- Smaller page size일 경우
- smaller internal fragmentation (paging system에서의 internal fragmentation은 항상 메모리의 마지막 페이지에서 발생한다. 같은 크기로 자르다가 마지막에 남을 수 있기 떄문)
- match program locality more accurately
- I/O시간이 줄어든다.(한 페이지가 들어오고 나가는시간이 size가 작기때문에)
- better utilization of memory
- Larger page table size
- I/O시간이 늘어난다.(총 페이지수는 늘어나기 때문에) <- 위에 줄어드는 특징과 tradeoff가 있지만 최종적으론 page size가 작아지면 I/O시간이 줄어든다.
- page fault가 늘어난다.(원래 하나의 페이지만 검사하면 될 걸 작은 사이즈 3개 page를 검사하는 경우)
최근엔 프로그램이 복잡해지고 커지기 때문에 page size를 키우는 추세라고한다.
Program restructuring
파란색 다 돌고, 노란색 다 돌고 ... 핑크색을 도는 것이 Row-major order고,
필기해둔거처럼 각 page마다의 첫번째행을 모두 돈 다음 각 page마다의 두번째행 이런식으로 접근하는 것이 Column-major order이다.
첫번째 사진에서 왼쪽처럼 코드를 짜면 zar배열을 Row-major order가 아닌 Column-major order로 접근하게 된다.
이렇게 Column-major order로 접근하면 page 접근을Row-major order보다 256배 많은 256x256번 하게되므로 page fault 확률도 256배 증가하므로 오른쪽과 같이 코드를 짜야한다.
-> Locality를 증가시킬 수 있는 방법 (ex. Row-major order)으로 코드를 짜야한다.
TLB Reach
TLB를 통해서 접근할 수 있는 메모리의 양으로 (# of entries) x (page size)로 구할수있다.
- For increasing TLB hit-ratio
- number of entries 증가시키기 <- 비싸다
- page size 증가 or provide multiple page sizes(8KB/4MB 혼합사용)
