3. 페이지 프레임의 할당 (page frame의 allocation)
Allocation problem: 각 process에게 얼마만큼의 page frame을 할당할 것인지에 대한 문제
allocation의 필요성
- 메모리 참조 명령어 수행 시 명령어, 데이터 등 여러 페이지를 동시에 참조한다. 명령어 수행을 위해 최소한 할당되어야 하는 frame의 수가 있음
- loop를 구성하는 page들은 한꺼번에 allocate되는 것이 필요함. 왜냐하면 최소한의 allocation이 없으면 매 loop마다 page fault나기 때문이다.
allocation scheme
- equal allocation(균등 할당) 모든 프로세스에게 똑같은 갯수 할당해주기
- proportional allocation(비례 할당) 프로세스의 크기에 비례하여 할당해주기
- priority allocation(우선순위 할당) 프로세스의 priority에 따라 다르게 할당 당장 cpu에서 실행될 프로세스와 그렇지 않은 프로세스를 구분하여 전자 쪽에 더 많은 페이지 프레임 할당
4. 전역교체와 지역교체(global replacement vs local replacement)
페이지 교체시 교체 대상이 될 프레임의 범위를 어떻게 정할지에 대해서 전역 교체(global replacement)와 지역 교체(local replacement)로 나뉜다.
global replacement(전역 교체) - 모든 페이지 프레임이 교체 대상
replace시 다른 process에 할당 된 frame을 빼앗아 올 쑤 있다.
process 별 할당량을 조절하는 또 다른 방법임
전체 메모리를 각 프로세스가 공유해서 사용하고 교체 알고리즘에 근거하여 할당되는 메모리의 양이 가변적으로 변하는 방법이다.
FIFO, LRU, LFU 등의 알고리즘을 global replacement로 사용 시 해당된다. 예를 들어 LRU를 global replacement로 쓴다고 하면 메모리에 올라와 있는 가장 오래 전에 사용된 페이지를 내쫓을 것이다. 이런 식으로 그 페이지가 어느 프로세스 소속인지는 상관하지 않고 다른 프로세스에 할당된 프레임을 빼앗아올 수 있다. 전체 시스템 차원에서 더 자주 참조되는 페이지가 메모리에 올라가기 때문에 프로세스의 프레임 할당량이 스스로 조절될 수 있는 것이다.
working set , PFF 알고리즘을 사용한다.
local replacement(지역 교체) - 현재 수행 중인 프로세스에게 할당된 프레임 내에서만 교체 대상을 선정할 수 있다.
얘는 프로세스마다 frame을 미리 할당하는 것을 전제로 한다. LRU를 프로세스 독자별로 운영해서 그 프로세스에서 가장 오래에 참조된 페이지를 내쫓는 것이 local replacement 예라고 할 수 있다. 아무튼 프로세스 독자별로 운영하면 local replacement가 된다.
5. 스레싱(Trashing)
프로세스의 원할한 수행에 필요한 최소한의 page frame 수를 할당받지 못했을 때 발생하는 현상. 집중적으로 참조되는 페이지들의 집합을 메모리에 한꺼번에 적재하지 못하면 페이지 부재율(page fault rate)가 크게 상승하여, cpu 이용률(cpu utilization)이 하락하게 되는 현상을 말한다.
- page fault rate가 매우 높아진다.
- cpu utilization이 낮아진다.
- os는 MPD(MultiProgramming Degree: 다중 프로그래밍의 정도- 메모리에 동시에 올라가 있는 프로세스의 수)를 높여야 한다고 판단한다.
- 또다른 프로세스가 시스템에 추가된다. (higher MPD)
- 프로세스당 할당된 frame의 수가 더욱 낮아진다.
- process는 page의 swap in / swap out으로 매우 바쁘다
- cpu는 대부분 한가함
- low throughput
MPD를 적절히 조절해 cpu 이용률을 높이고 스레싱 방지하는 방법에는
- working set 알고리즘
- page fault frequency scheme
Working Set 알고리즘
* Locality of Reference
- 프로세스는 일정 시간동안 특정 주소 영역을 집중적으로 참조하는 경향이 있다. 집중적으로 참조되는 해당 page들의 집합을 locality set이라고 한다.
* working set algorithm
- locality set이 메모리에 동시에 올라갈 수 있도록 보장하는 메모리 관리 알고리즘
* working-set model
- Locality에 기반하여 프로세스가 일정 시간 동안 원할하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 page들의 집합
- working set 모델에서는 process의 working set 전체가 메모리에 올라와 있어야 수행되고 그렇지 않은 경우 모든 frame을 반납한 후 swap out(suspend)한다. = 프로세스의 working set을 구성하는 페이지들이 한꺼번에 메모리에 올라갈 수 있는 경우에만 그 프로세스에게 메모리를 할당한다. 그렇지 않은 경우에는 프로세스에게 할당된 페이지 프레임들을 모두 반납시킨 후 그 프로세스의 주소 공간 전체를 디스크로 스왑 아웃 시킨다.
working set Algorithm
* working set의 결정
- working set window를 통해 알아낸다.
- window size가 Δ(delta)인 경우
시작 t1에서 working set ws(t1)
- time interval(ti - Δ, ti)사이에 참조된 서로 다른 페이지들의 집합
- working set에 포함된 page는 메모리에 유지, 속하지 않은 것들은 버린다. 즉, 창조된 후 Δ시간 동안 해당 page를 메모리에 유지한 후 버린다.
working set algorithm은 메모리에 올라와 있는 프로세스들 워킹셋 크기의 합이 프레임의 수보다 클 경우 일부 프로세스를 스왑 아웃 시켜서 남은 프로세스의 워킹셋이 메모리에 모두 올라가는 것을 보장한다. => MPD 줄이는 효과 발생
- working set을 다 할당하고도 page frame이 남는 경우
swap out 되었던 프로세스에게 working set을 할당(MPD를 높임)
Window size Δ
- working set을 제대로 탐지하기 위해서는 window size를 잘 결정해야 함
- Δ 값이 너무 작으면 locality size를 모두 수용하지 못할 우려가 있음
- Δ 값이 너무 크면 여러 규모의 locality set 수용, but MPD가 감소해 cpu 이용률이 낮아질 우려가 있다.
- Δ 값이 무한이면 전체 프로그램을 구성하는 page를 working set으로 간주한다.
워킹셋 알고리즘에서 워킹셋의 크기는 시간이 흐름에 따라 변한다.
Page Fault Frequency scheme (PFF)
PFF는 page fault rate의 상한값(upper bound)과 하한값(lower bound)을 둔다.
- page fault rate가 상한가(upper bound)를 넘으면 frame을 더 할당한다. 이 프로세스에게 할당된 프레임 수가 부족하다고 판단되기 때문에ㅇㅇ
- pafe fault rate가 하한가(lower rate) 이하면 할당 frame 수를 낮춘다. 필요 이상으로 많은 프레임이 할당된 것으로 간주
- 빈 frame 없으면 일부 프로세스를 swap out 시킨다.
page size의 결정
* page size를 감소시키면 페이지 수는 증가한다. 페이지 테이블 크기도 증가한다. 내부 조각 (internal fragmentation) 감소, disk transfer의 효율성도 감소한다. seek/rotation vs transfer
* 필요한 정보만 메모리에 올리는 것이 메모리 이용에 효율적이다. locality 활용 측면에서는 좋지 않다.
요즘 트렌드는 lager page size라고 한다....
'CS > operating system' 카테고리의 다른 글
| Disk Management: 디스크 관리 (2/2) (0) | 2021.02.24 |
|---|---|
| Disk Management: 디스크 관리 (1/2) (0) | 2021.02.23 |
| Virtual Memory: 가상 메모리 (1/2) (0) | 2021.02.19 |
| Memory Management: 메모리 관리 (3/3) (0) | 2021.02.18 |
| Memory Management: 메모리 관리 (2/3) (0) | 2021.02.17 |