3. Allocation of Frames

각 프로세스는 minimum number of pages 가지고 있다.
instruction set architecture에 의해 정의된다.

Ex 1. 1-level indirect addressing : 3 frames
Ex 2. PDP-11 : 6 frames (MV from, to)
(instruction 6 byte(not 2^n) 2 pages, 2 pages to handle from, 2 pages to handle to)

Frame Allocation Algorithm

Equal allocation

100개 frame, 5개 process --> 각 20개씩 동등하게

Proportional allocation

더 많은 page 요구하는 process에게 더 많은 frame 할당

multiprogramming level 필요할수도

Priority allocation

우선순위

Global vs. Local Replacement

어떤 것을 replace할 것인가

Global replacement

모든 frame 중에서
자신의 page fault rate를 control할 수 없다.(남이 내 걸 replace해버리는 경우 발생)
일반적인 경우! 앞에서 설명한 경우!

Local replacement

자기의 set 된 frame 중에서
내가 내 걸 잘 control할 수 있다.
하지만 나는 page fault가 계속 일어나는데 다른 애는 하나도 안 일어나고 그러면 사용되지 않은 page가 낭비될 수 있다.

4. Thrashing

수행하는 것보다 메모리 swap in-out하는 시간이 더 많이 발생하는 경우
--> 프로세스에게 할당된 frame이 너무 작을 경우 발생

local replacement 쓰면 해결할 수도 있긴 하지만,
어떻게 thrashing이 일어나지 않게 할까?

Locality of a Process Execution

thrasing을 방지하려면 프로세스에게 필요한만큼 frame을 할당해주어야 한다.

얼마나 많은 frame이 필요한지 어떻게 알까?
프로세스가 실제로 얼마나 사용하는지 보면 된다.

Locality model
프로세스는 locality 지역성이 있다
프로세스는 옮겨가면서 작동한다.

locality size보다 큰 frame을 할당해주면 thrasing 방지 가능하다.

Working Set

△델타를 working set window라고 한다.
이는 특정시점 기준 page reference가 몇 번 일어났는가를 체크하기 위한 크기이다.
델타 범위 안에서 누가 access하는지 reference table을 보고 알 수 있다.

이 window를 옮겨가면서 새로운 working set에 대해서도 계속 업데이트한다.

working set은 locality의 추정치이다.

델타의 시간 동안 필요한 frame(working set) 개수를 통해 얼마나 frame을 할당해야할지 알 수 있다. (working set size)

델타가 너무 작으면, locality를 파악하기 어렵다.
델타가 너무 크면 locality가 겹칠수도 있다.
델타가 무한대라면 그냥 전체 프로그램에 해당하는 것.

D = sum of WSS = total demand for frames
모든 수행중인 process의 WSS합은 필요한 frame 수

D > m(사용가능한 frmae 수)이면, 즉 필요한 것보다 사용할 수 있는 게 적으면 thrasing이 발생한다.

OS는 각 process마다 working set을 확인하고, page fault가 일어났을 때 D > m인지 확인한다.
D>m일 때 프로세스를 보류/미루고, 그 프로세스가 사용하고 있던 frame을 다른 프로세스에게 재할당한다. 따라서 page fault 덜 일어난다.

얼마나 자주, 어떻게 working set을 설정할까?

How to Monitor Working Set

각 page reference마다 매번 working set 설정하는 방법 -- 너무 expensive
...?

working set 구현이 쉽지 않아 page fault frequency 방법을 사용한다.

Page-fault Frequency Scheme

5. Memory-Mapped Files

Memory mapped file I/O는 disk 블럭을 메모리의 페이지로 mapping 시키는 것처럼 file I/O
file I/O를 메모리 access 하는 것처럼

read() write() system call보다 더 간단하게 할 수 있다...?

파일과 메모리를 매핑한다
매핑하는 대상이 파일이다

6. Other consderation

Pre-Paging

맨 처음 초기에 page fault를 대비해 한꺼번에 미리 가져오는 것
정확한 예측 필요, overhead가 효율적일까

일반적으로 page fault 줄일 수 있다.

page size selection

• fragmentation : page size 크게 하면 interanl fragmentation 늘어난다
• table isze : smaller page는 page table 사이즈가 커진다(entry)
• I/O overhead : 한번 읽어들여도 되니까 큰 페이지 사이즈는 I/O time을 줄일 수 있다. 하지만 response time이 길어질 수도 있다.
• Locality : 작은 페이지 사이즈는 locality 세밀하게 표현할 수 있다

TLB Reach

TLB로부터 access하는 메모리 크기

TLB reach = TLB size X page size

Program structure cna affect the performance

I/O interlock