Page Replacement_운영체제(11)

Page Replacement

• page fault가 발생하면 OS는 fault page를 disk에서 읽고 check해서 memory frame에 올린다.
• process가 자신에게 할당된 page frame들을 전부 사용했다면 OS는 다른 page를 replace(evict)한다.
• victim page : evict 된 page
• 가장 필요 없을 것 같은 page frame을 evict해야한다.

Evict the best page

• 앞으로 다시는 접근하지 않을 page를 evict하는 것
• 이러한 page를 아는 것은 불가능하기 때문에 예측을 하여 evict한다.
• 가급적 사용되지 않을 확률(정도)가 높은 page를 evict한다.
• Belady는 가장 오랫동안 사용되지 않을 page를 evict하는 것이 가장 optimal한 방법이다.

Belady’s Algorithm

• 가장 오랫동안 사용되지 않을 page를 evict하는 방법
• 미래를 예측하는 것이 불가능한 문제점이 있는데, 이러한 알고리즘을 off-line algorithm이라고 한다.
• 실행중에는 적용할 수 없다.
• 프로그램을 실행할 때, memory page number의 기록을 memory reference log라고 하는데, 이 log를 확인하는 방식이다.
• offline algorithm은 online algorithm의 성능을 판별할 수 있는 척도가 된다.

FIFO

• 가장 메모리에 올라온 시간이 오래된 page를 evict하는 방법
• 가장 simple한 방법
• 메모리에 오래전에 올라왔지만 중요한 page는 지속적으로 사용될 가능성이 있기 때문에 부적절할 수 있다.

FIFO - Belady’s Anomaly

• main memory를 확장을 하였는데 fault가 줄지 않고 오히려 증가하는 현상

LRU(Lease Recently Used)

• 사용된 시간이 가장 오래된 메모리를 evict
• 과거의 상황을 보면 미래의 행동을 예측할 수 있다는 방식
• implementation
  • Counter implementation : timestamp를 이용하여 관리
  • Stack implementation : stack을 이용하여 관리
  • 실질적으로 overhead가 커서 사용하지 못한다.

Approximating LRU

• (R)bit : reference bit로 page를 read/write 등 접근을 했을 때 사용되었다는 것을 표시하는 bit
• (R)bit를 참조하여 사용
• 각 page에 counter를 둔다.
• 지정한 interval마다 전체 page를 scan한다.
• R = 0 : counter를 증가시킨다.
• R = 1 : counter를 0으로 만들고 R bit를 clear한다.
• counter 값이 가장 큰 page를 evict한다.
• R bit가 없다면 valid bit를 사용하여 fault를 발생시켜 판단하기도 한다.

Second Chance / LRU Clock

• Approximating LRU 또한 overhead가 크기 때문에 생각한 방식
• R=1이라면 한번 살려주고 0으로 바꾼 뒤 다음으로 넘어간다.
• 만일 모든 page가 R = 1이라면 전체를 1바퀴 순회하고 제일 처음 page가 evict 될 것이다.
• LRU의 성능과 근사한 방식이다.
• 정확도가 memory의 page 수에 따라 달라진다.
• page수가 적으면 LRU와 근사하지만, page가 많으면 전체 순회시간이 길어지기 때문에 시간 정밀도가 떨어진다.

Not Recently Used / Enhanced second chance

• 최근에 사용되지 않은 것
• M bit : page가 modified(dirty) page인지 clear page인지 check하는 bit
• clock interrupt를 주기마다 발생하는데, 이 때마다 R bit를 clear한다.
• 가장 낮은 class를 evict한다. reference도 되지 않았고 modify도 되지 않았기 때문

LFU (Least frequently used)

• 사용빈도, 얼마나 사용되었는 가를 확인한다.
• clock interrupt마다 R bit를 확인하고 이를 page의 counter 정보에 더한다.

Allocation of Frames

Fixed space algorithms

• local replacement : 각 process에게 일정한 크기의 memory를 처음에 할당한다. 만일 자신이 할당받은 memory를 다 쓴 상태에서 fault가 발생하면, 자신이 할당받은 것 중에서 victim을 설정하는 방식
  • process마다 필요한 frame이 다르기 때문에 역차별이 발생할 수 있다.

Variable space algorithms

• global replacement : process마다 고정된 크기가 아닌 필요 양에 비례해서 할당하는 방식, 전체에서 victim을 설정하는 방식
  • 지속적으로 1개의 process가 희생하는 상황도 발생할 수 있다.

Thrashing

• disk로 fault가 다녀가기 때문에 system은 과부하인 상황이라고 생각하고 OS가 I/O가 계속 일어난다 생각해서 CPU 사용량이 낮다고 착각을 하게 된다.
• 이러한 현상 때문에 메모리 과부화 상황을 더욱 가속화시키는 현상
• 너무 빈번하게 page fault가 발생하여 CPU utilization이 낮아지는 현상

Working Set Model

• 현재 process가 필요해서 확보해야하는 page의 집합
• WorkingSet(t, w) = time interval(t-w, t) 간의 page 수
• t : time, w : working set window size

Working set size(WSS)

• working set 내부의 page 개수가 working set size
• program의 locality에 따라 변한다.
• locality가 좋다면 들어오는 page수가 작아지고 working size가 커진다.
• 불필요한 page fault를 최소한으로 만드는 것이 목표이다.
• wss의 전체 total은 현재 system이 제공하는 frame의 개수보다 넘는다면 누군가는 메모리 부족으로 인해 문제가 생긴다고 예상할 수 있다. 이러한 경우 process를 중단시킨다.
• 중단된 process는 이 process를 다시 추가해도 memory 양에 문제가 없을 때 넣는다.

Working set page replacement

• 각 process마다 clock(current virtual time)을 두고 측정한다.
• CPU를 사용한 시간마다 virtual time이 증가한다.
• last use time을 각 PTE에 기록하고, 일정 시간마다 interrupt를 발생시켜 R bit를 clear한다.
• 한 interval 내에 새롭게 reference가 되어야 유용한 페이지라고 판단한다.
• R = 1 : R = 0으로 초기화하고 Tlast에 Tcurrent를 기록한다.
• R = 0 and (Tcurrent – Tlast > 기준 값 t) : evict

PFF(Page Fault Frequency)

• 얼마나 Page fault가 많이 발생하는가
• fault 발생률이 threshold보다 높다면, memory를 증가하던가 process를 내리던가 조치한다.
• fault가 기준 이하라면 사용하던 memory(frame)를 회수하는 방식도 존재한다.
• PFF가 증가하고 free frame이 없다면 process를 중단하는 방법을 사용해야한다.

Advanced VM Functionality

Shared Memory

• shared memory의 기본 할당 단위는 1개의 page이다.
• shmget(key, __)를 통해 shared memory에 접근(할당)을 한다.
• 각 process의 table에 있는 PTE는 shared memory의 같은 physical frame을 가리켜야한다.
• 만일 mapping하는 자리가 사용하고 있다면 fail

Copy On Write

• child가 write를 하는 시점에만 copy를 하는 방식
• process creation(fork)를 진행하면 process와 동일한 clone이 생성된다.
• 이 때, 모든 memory를 copy하는 것이 아니라 부모가 가리키는 page(frame)을 자식도 동일하게 가리키도록 한다.
• 자식이 읽기만 하면 이러한 상황 그대로 두면 되지만, 만일 data를 write하려고 하면 해당 frame(page)만 copy를 하여 사용하도록 한다.

vfork() system call

• memory address space를 부모와 공유하는 process를 생성할 때 사용한다.
• parent execution은 block이 되었다가 child가 exit or 새로운 program에 execute할 때(exec) 해제된다.
• 주로 exec()을 통해 다른 process로 바뀐다고 보장할 때 사용한다.

Memory-mapped files

• read/write와 동일한 방식으로 file access를 지원하기 위한 방식
• file을 virtual memory region(virtual address)에 matching하여 사용한다.
• mmap()을 사용하여 virtual address memory region에 file을 bind한다.
• write했을 때 바로 disk에 반영되지 않는다. 먼저 kernel buffer에 전달이 되고, 이 정보들이 disk로 간다.
• virtual address base + N은 file의 N offset의 위치를 나타낸다.
• kernel buffer(physical memory)가 pageout(replace)되는 경우에 모든 update를 한꺼번에 disk에 옮기고 내놓는다.
• I/O를 효과적으로 할 수 있다.
• page가 dirty page가 아니라면 disk로 update(write)가 불필요하다.

Advantages

• pointer만을 사용하여 file과 memory에 접근하는 것을 동일하게 할 수 있다.
• copying이 적다. → 약 3번의 copy가 사라진다.
• 여러 process가 공유를 하기 쉽다.

Drawbacks

• process가 data를 이동하는 것에 대해서 절대적인 권한을 가지지 못한다.
• 일반 file 말고 pipes, sockets은 memory mapped file 방식으로 사용하지 못한다.