this->OS.code(13)

<Multli-level Page Table>

process의 크기∝page table 크기∝page entry수 이기에 paging이 단점이 될 수 있다

pagingi은 page table이 필수로 필요해서 별도의 메모리자원할당이 필요하다.

- sol_1. multi-level page table (= hierarchical page table)

- sol_2. Inverted page table

 

<Two-Level in 32-bit address>

 

<Two-Level Paging>

 

<TLB: Translation Lookaside Buffer = associative memory>

최근에 access한 process page frame#을 저장하는 cache

page#과 Frame#을 한 쌍으로 저장하는 방식.

- 32bit address의 경우, page가 2계층인데 가상주소공간⇑=>page table⇑=>계층⇑=time consuming⇑

- 다계층 page table을 가진 demand paging방식에서 page table을 읽는데 걸리는 시간을 줄이는 방법

TLB hit: cache에 원하는 정보가 존재

TLB miss: cache에 원하는 정보X (outer page table-> page table-> process page로 메모리 access 필요)

<Effective Access Time: TLB의 process 접근 평균시간>- page fault 발생은 하지않을 때

RAM access time = 1 μs , TLB내용 읽는 시간 = ε , Hit ratio = α (0 ≤ α ≤ 1)

TLB hit = ε+1μs

TLB miss = ε+1μs+1μs (TLB에 있는지 확인 + memory에 있는 page table ＋ 실제 메모리)

EAT = (ε+1μs)α + (ε+1μs+1μs)(1-α) = 2μs + ε - α

단, TLB가 없으면 2μs이기에 α >> ε 임을 알 수 있다.

또한, for나 while과 같이 반복문에서 반복횟수가 늘어날수록 α⇑

 

 

 

 

<Page Replacement>

demand paging의 경우 필요한 page를 메모리에서 그때그때 가져와야 하는데, 만약 memory frame에 빈공간이 없으면 들어와 있는 memory를 보조기억장치로 보내고 빈공간을 만들어야해서 page replacement algorithm이 사용된다.

 

가상메모리의 경우, disk같은 보조기억장치의 가상주소공간을 만들어 필요한 page만 메모리로 가져와 실행하는데, 만약 메모리 frame이 다 차버리면 어떤 것을 replace 할것인지 중요하다.

<EAT_Demand paging>

page fault: process가 실행시 주소를 access할 때, 대상 page가 메모리에 없을 때 발생

page fault가 발생할 확률 page fault rate를 p라 하자. 이때 EAT는 다음과 같다.page fault: process가 실행시 주소를 access할 때, 대상 page가 메모리에 없을 때 발생한다.

page fault가 발생할 확률 page fault rate를 p라 하자. 이때 EAT는 다음과 같다.

EAT = (1-p)⦁memory access + p⦁{page fault overhead + [swap page out] + swap page in ＋ restart overhead }

이때, 1-p일 때, memory access는 disk에 갈 필요가 없기 때문이고

page fault overhead는 page fault interrupt 처리+replacement algorithm 시간

swap page out은 쫓아내는 시간으로 modified bit=0일 때, 생략될 수 있다.

swap page in은 필요한 page를 읽어오는 시간이며

restart overhead는 instruction을 재실행하는데 걸리는 시간이다.

 

<Degree of multiprogramming>: main memory에 들어있는 process 수로 

고정분할, 동적분할방식에 비해 가상메모리 방식을 사용할 때가 더 값이 큼

 

 

<Thrashing>

CPU utilization이 갑자기 떨어지는 구간으로 다음과 같은 원인이 있다.

locality(working set) 크기 > 전체 memory 크기

[locality]: process에서 code, data같은 반복적으로 access해야하는 부분

<Thrashing 해결책: Process Suspension>

보조기억장치로 이동시키는 방법으로 swap out, swap to disk라 표현하기도 한다.

낮은 우선순위, 현재 page fault된 process, 가장 큰 크기 process와 같은 기준으로 process suspension 진행