Kwonlog
로그인
Kwonlog
로그인
Page Replacement_운영체제(11)
조권휘
·
2023년 1월 4일
팔로우
0
OS
Operating Systems
운영체제
0
운영체제
목록 보기
11/14
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 방식으로 사용하지 못한다.
조권휘
안녕하세요 :) Data/AI 공부 중인 한국외대 컴퓨터공학부 조권휘입니다.
팔로우
이전 포스트
Address Translation_운영체제(10)
다음 포스트
File Systems Interface_운영체제(12)
0개의 댓글
댓글 작성