OS: Paging

Paging 이란?

          > 프로세스를 작은 고정크기의 partition을 나누는 것을 말한다

                    >> Physical Memory의 이 공간을은 frame 이라 부른다

                    >> Page size = frame size

                    >> 전체 프로세스는 여전히 메모리에 로드되어 있다

                    >> 하지만 연속적일 필요는 없다

                    >> 가상 주소는 페이지 수와 페이지의 시작에 offset으로 구성된다.

          > Segmentation이랑 비교 했을 때 paging 은

                    >> 할당과 swapping 이 더 쉽다

                    >> No external fragmentation

 

Paging 구현

         

 

          > Page Table 은 특정 프로세스의 모든 페이지를 기록

                    >> 각 entry는 메인 메모리에 있는 알맞는 frame을 가지고 있다

                    >> Protection bit 을 가질 수 있으나 비효율적

          > Segmentation 보다 HW 지원이 덜 필요하다

                    >> limit에 대한 기록 필요 x

 

Frame Example 

Managing Pages and Frames

          > OS는 보통 free frames를 bit map을 통해 기록해 둔다

                    >> 1: free, 0: allocated

                    >> free frame 을 찾기 위해 첫번째 1bit을 찾는다

          > Page table base pointer는 실행중인 프로세스의 페이지 테이블을 가르킨다

                    >> context switch와 함께 저장되고 복구된다

                    >> Page Table 은 다음 내용 또한 가지고 있다

                              <Valid bit: 페이지가 프로세스의 가상 주소 공간에 올라가 있는지>

                              <Demand Paging: 추후 다룰 예정>

        

Evaluation of Paging

#Advantage

          > 메모리 할당이 쉽다

                    >> 사용가능한 frame의 리스트를 만들어 두고 첫번째 free frame 을 가져온다

          > swap 하기 쉽다

                    >> Page, frame은 같은 크기

          

#Disadvantage

          > Page Table 은 크다

                    >> 대부분의 page table 들은 레지스터에 저장하기에 너무 크다 --> 물리적 메모리에 할당

                    >> 각 주소변환마다 extra memory reference 가 필요

          > Internal Fragmentation

                    >> 항상 전체 페이지를 받는다

                    >> 큰 페이지는 문제가 더 심각

                    >> 평균적으로 1/2 page per profess

 

#Demand Paging

          > 지금까지는 paging 이든 segmentation 이든 모두 main memory 에 올라가 있어야 했다. 

          > 근데 virtual memory 의 small subset 만 접근해도 되지 않을까?? -> Demand Paging

 

          > Virtual memory pages are stored in either

                    >> Frame of physical memory

                    >> Disk

          > 프로세스는 가상 주소공간의 일부만 가지고 run 가능

          

          > Starting a New Process

                    >> 프로세스는 0 이상의 가상 page를 physical memory에, 나머지를 디스크에 둔 상태로 시작

                    >> Page Selection: 언제 새로운 페이지를 physical memory에 올릴까?

                              - Prepaging: Pre-load enough to get started

                              - Demand Paging: start with 0 pages and load evey page fault occurs

                    >> Demand paging works due to locality of reference

          > Page Fault

                    >> Physical memory에 없는 페이지에 접근하려할때 발생

                    >> Page table must have present(valid) bit for each page

                    >> Attempt to access page with no valid bit causes page fault ( exception which causes trap in OS)

                    >> When page fault occurs

                              - OS는 페이지를 디스크에서 꺼내와야 한다

                              - OS는 페이지 테이블을 update & set present bit

                    >> Interrupt랑 달리 page fault 는 memory reference 가 있을때 마다 발생 가능하다

                              - Even in the middle of instructions

                              - However, handling page fault must be invisible to the process

          > Handling Page Faults

                    >> Page fault handler must be able to recover enough of the machine state to continue executing the program

                    >> PC is usually icremented at the beginning of the instruction cycle

                              >> if OS or hardware does not do anything special, faulting process will execute next instruction

               

          > Performance of Demand Paging

                    >> Effective access time (eacc) = (1-p)(macc) + p (pfault)

                              - p = prob of page fault

                              - macc = memory access time

                              - pfault = time needed to service page fault

          

          > Page Replacement

                    >> OS가 새로운 프로세스에 할당할 프레임이 필요하고, 모든 프레임이 사용중이라면, 하나의 페이지를 골라 교체한다

                    >> By having CPU set dirty bit to page that has been modified -> reduce overhead

                              -> only copy data back with dirty bit

                  

 

          > Page Replacement Policy

                    >> Random

                    >> FIFO

                    >> Optimal: 가장 나중에 참조될 페이지 선택 (사실상 불가능)

                    >> Least Recently Used: 가장 오래 참조되지 않은 페이지 선택                 

          

          > Implementing LRU

                    >> 모든 페이지에 clock register (for ones in physical memory)

                    >> 한번의 접근마다 clock update

                    >> 교체가 일어나면 lowest clock vaue 를 찾는다

                    >> FIFO(NRU)

                              - Use R(reference bit) and set it whenever page is referenced

                              - Clear R bit periodically (ex: every clock interrupt)

                              - Choose any page with clear R bit

                    >> Clock / Second Chance Algorithm

                              - Use R bit and set it whenever page is referenced

                              - Page fault 가 일어나면 모든 페이지의 clock을 조사

                                        - 마지막으로 조사한 페이지에서 시작

                                        - 해당 페이지에 R bit 이 있다면 clear it

                                        - 해당 페이지에 R bit 이 clear 라면 replace it

                    >> Least Frequently Used (LFU) / N-th chance algorithm

                              - Don't evict unless page has been swept n times

                              - Use R bit and counter

 

          > Frame Allocation

                    >>  각 프로세스가 몇개의 frame 을 할당받을까? (M frames, N processes)

                              - 최소 2 frame(instruction, memory operand)

                              - 최대는 number in physical memory

                    >> Allocation Algorithm

                              - Equal allocation : each gets M/N frames

                              - Proportinal allocation: Number depends on size and priority             

                    >> 어떤 pool 에 있는 프레임을 교체하는가?

                              - Local: 프로세스는 각자의 프레임만 교체 / 재사용 가능하다

                              - Global : 어떤 프레임이든 사용 가능

 

          > Thrashing

                    >> 프로세스가 한번 run 하고 난 뒤, 다시 run 하기 전 해당 프로세스의 모든 page 가 paged out 될 수 있다.

                    >> 다음번에 프로세스가 실행될 때, OS 는 여러번의 page fault 경험

                    >> 이렇게 낭비되는 행동을 thrashing 이라 함

                    >> Thrashing 은 모든 프로세스 요구사항의 합이 물리주소보다 크면 발생

                    >> 해결방안

                              - 프로세스에게 필요한 만큼의 frame 만 할당

                              - 시간에 따라 할당된 프레임의 수를 조절

                              - 너무 높아지면 해당 프로세스 suspend

                    >> Working set: 프로세스가 돌기 위해 필요로 하는 페이지