물리적인 메모리의 주소 변환은 운영체제의 역할이 없었지만, virtual memory 기법은 전적으로 운영체제가 관여를 하고 있다.
Demand Paging
요청이 있으면 그 페이지를 메모리에 올린다는 것이다.
본 챕터에서는 paging 기법을 사용한다고 가정한다.
장점
- I/O 양의 감소
- 프로그램을 구성하는 주소 공간 중 빈번히 사용되는 부분은 굉장히 제약적이다.
- 좋은 SW일수록 굉장히 방어적이기 때문에 그러한 코드들이 대부분을 차지한다.
- 그래서 이러한 부분들은 사용이 안되는데 모두 메모리에 올려놓는다면 굉장히 낭비가 될 것이다.
- 하지만 요청이 올 때만 메모리에 올리게 된다면 굉장히 효율적일 것이다.
- Memory 사용량 감소
- 빠른 응답 시간
- 생각하는 관점에 대해서는 조금 다를 수 있다.
- 미리 통째로 올려놓으면 접근시에 더 좋은 것 아닌가
- 한정된 메모리 내에서 효율을 생각해 부분적으로 페이지를 메모리에 올림으로써 I/O 양이 감소하고 메모리 사용량이 감소함을 통해 응답시간이 빨라짐을 의미한다.
- 더 많은 사용자 수용
프로그램을 구성하는 페이지들 중에서 당장 필요한 부분은 물리 메모리에 올라가고 필요하지 않은 경우는 swap area에 내려가 있게 된다 .
따라서 물리 메모리에 실제로 올라가 있는 페이지들은 valid이고, swap area에 내려가 있는 것은 invalid로 표시된다. 또한 사용하지 않는 주소인 경우 invalid로 표시된다. (A-F까지 사용하는 것인데, 주소공간만큼 할당되기 때문에 G,H가 생겼다. 따라서 G,H는 해당 프로그램이 사용하지 않는 공간이기 때문에 invalid이다. G,H가 어떻게 사용되지 않는지 알 수 있는가? 물리 메모리, backing store 어디에도 보이지 않기 때문이다. )
B 요청 -> page table 확인 -> invalid -> backing store에서 물리 메모리로 올려야 한다. 이 작업은 사용자 프로세스가 해결하지 못한다. 이러한 상황을 page fault라 하며 CPU는 자동으로 운영체제로 넘어간다. 즉, SW interrupt라 할 수 있다.
Page Fault
- Invalid page 접근 -> MMU 가 trap 발생
- CPU가 kernel mode로 들어감(운영체제로 넘어감) -> page fault handler 실행
- invalid reference인지 확인 (ex. bad address, protection violation) => abort process or 다음 단계
- 빈 페이지를 하나 획득 (물리 메모리가 모두 차 있으면 뺏어와야함)
- 해당 페이지를 disk에서 memory로 읽어온다.
- disk I/O가 끝나기 까지 이 프로세스는 CPU를 preempt 당함(block) -> disk controller에게 읽어오라 부탁
- disk read가 끝나면 page tables entry 기록(frame, valid), valid/invalid bit = "valid"
- ready queue에 process를 insert -> dispatch later
- 이 프로세스가 CPU를 잡고 다시 running
- 중단되었던 instruction 재개
디스크로 접근하는 것은 굉장히 오랜시간이 걸리는 일이기 때문에 page fault의 비율이 메모리 접근 시간 결정에 큰 요소이다.
p : page fault rate ( 0 <= p <= 1)
- p = 0 : no page faults
- p = 1 : every reference is a fault
- 보통은 p가 0에 가깝다
ma : memory access
page fault time : OS & HW page fault over head + swap page out if needed (만약 자리 없어서 빈 frame 뺏을때) + swap page in + OS & HW restart overhead
Page replacement
빈 frame이 없는 경우 어떤 frame을 뺏어올지 결정하는 것으로 운영체제가 하는 일이다.
곧바로 사용되지 않을 page를 쫓아내는 것이 좋다.
페이지를 쫓아냈더니 금방 다시 호출된다 => 안좋음
replace algorithm
page replace하는 알고리즘으로 p를 0에 가깝게 만드는 것이 목표이다.
만약 victim이 disk에서 메모리로 올라와서 부터 쫓겨날 때 까지 write가 없었다면, 쫓겨날 때 그냥 지워버리면 된다. 하지만 write가 발생했다면 disk에도 write 하고 쫓겨난다. 그리고 쫓겨날 때 invalid로 바꿔준다.
Optimal Algorithm
미래에 참조되는 page들을 이미 안다고 가정 => 실제 시스템에서 사용될 수 없음 => offline algorithm
가장 먼 미래에 참조되는 page를 쫓아낸다. 미래를 모두 알기에 가능한것이다. 총 9번의 page fault가 일어난다. 어떠한 알고리즘을 사용하더라도 9번보다 page fault가 덜 일어날 수 없다.
실제 시스템에서 사용하는 다른 알고리즘에 대한 upper bound를 제공한다. 아무리 좋은 알고리즘을 만들어도 이것 보다 성능이 좋을 수 없다. 하지만 이와 성능이 비슷 -> 더이상 좋은 알고리즘을 만들 수 없음
FIFO Algorithm
미래를 모를 때 사용, First In First Out 알고리즘으로 먼저 온 것을 먼저 쫓아ㅐㄴ는 알고리즘이다.
frame의 크기를 3 -> 4처럼 늘릴 때 성능이 더 좋아지지 않고 page fault가 더 많이 발생하는 기이한 현상이 생길 수 있다.
LRU(Least Recently Used)
제일 오래전에 사용된것을 쫓아낸다.
최근에 참조된 페이지가 가까운 미래에 다시 참조되는 성향을 이용
LFU (Least Frequently Used)
참조 횟수가 가장 적은 페이지를 지운다.
과거에 도둑질을 많이 한 사람은 미래에도 많이 할 것이라는 성질이다.
-
최저 참조 횟수인 page가 여럿 있는 경우
- LFU 알고리즘 자체에선 여러 page중 임의로 선정
- 성능 향상을 위해 가장 오래전에 참조된 page를 지우게 구현할 수 있다.
장단점
-
LRU 처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기 때문에 page의 인기도를 좀 더 정확히 반영할 수 있음
-
참조 시점의 최근성을 반영하지 못함
-
LRU보다 구현이 복잡
Reference string
1,1,1,1,2,2,3,3,2,4,5(현재)
frame = 4
현재 5번 page를 보관하기 위해 어떤 page를 삭제해야하는가?
LRU는 1번을 쫓아낸다. -> 1번은 가장 오래전에 참조되긴 했지만 굉장히 많은. 참조가 있었음을 반영하지 못한다.
LFU는 4번을 쫓아낸다. -> 4번은 참조회수가 1번이지만 이제 막 시작하는 아이인데 고려하지 않고 지워버린다.
LRU 구현
가장 밑에 있는 page가 가장 최근에 사용된 것이고 맨 위에 있는 것이 가장 오래된 page이다. 따라서 제거될 때 제일 위에 있는 page를 삭제하면 된다. 또한 참조될 때 마다 맨 밑으로 내려가 순서가 바뀐다.
LRU, LFU
구현
Double linked list로 구현하였다.
LRU는 참조되는 순간 맨 밑으로 내려가면 되는데 LFU는 자신 보다 덜 호출된 page들 밑에 있어야 하므로 내려가면서 page들과 자신을 비교해야한다. 따라서 LRU는 O(1)의 시간 복잡도를, LFU는 O(n)의 시간 복잡도를 지닌다.
그래서 LFU는 Double linked list로 구현하지 않고 heap을 사용해 구현해 O(log n)의 시간복잡도를 가지게 한다.
heap은 이진트리로 자식이 두개씩 있다. 맨 위에는 참조횟수가 가장 적은 page를 넣고 밑으로 갈수록 참조 횟수가 많게 하면 된다. 1줄 세우기와는 다르게 자식 두개 중에만 비교 하면서 내려가면 된다. 자식 둘 모다 참조횟수가 많이 않을 때 까지 내려가면 된다. 이 전체의 높이가 log2의 n이 므로 비교횟수가 많아 봐야 logn이 된다. 그리고 쫓아낼 때는 맨위에 있는 것을 쫓고 노드를 재 구성하면된다.
log n과 n의 차는 굉장히 크다.
Caching
한정된 빠른 공간(cache)에 요청된 데이터를 저장해 두었다가 후속 요청시 cache로 부터 직접 서비스 하는 방식
paging system : cache -> 물리적인 메모리, 느린 공간 -> backing store
cache memory(일반적인 메모리 참조에서 사용, CPU에서 메모리로 접근할 때 직접접근 하는게 아닌 CPU와 메모리 사이에 cache를 메인 메모리에 접근하기전 cache를 먼저 살펴봄), buffer caching(파일 시스템에 대한 read/write 요청을 메모리에서 빠르게 서비스하는 방식), Web caching(웹 페이지에 대한 요청을 하면 멀리 있는 서버에서 가져와서 디스플레이 하게 되는데, 동일한 url에 대해 지금도 요청, 잠시 후에도 요청하게 되면 최초의 요청 시 내 컴퓨터에 저장해두었다가 잠시 후 요청할 때 저장되어있던 것을 보여주는것) 등 다양한 분야에서 사용
cache memory, buffer caching는 단일 시스템에서 저장매체간의 속도차이가 나서 사용
Web caching은 지리적으로 멀리 있기 때문에 오래걸림
시간 제약
replace algorithm에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 없음
Buffer caching이나 Web caching의 경우 O(1)에서 O(log n)정도까지 허용
=> 따라서 위에서 Double linked list로 LFU를 구현해 O(n)의 시간복잡도를 가졌었다. 하지만 이는 caching에서는 시간제약에 걸려 사용하지 못한다는 것이다.
Paging systme인 경우
- page fault인 경우에만 운영체제가 관여함
- Disk에 접근해야하므로 CPU의 제어권이 운영체제로 넘어가 disk에 있는 페이지를 물리적인 메모리로 올린다. 이때 물리적인 메모리가 가득 차 있다면, 어떤 page를 쫓아내야한다. 하지만 LRU를 사용한다면 가장 오래전에 참조된 page를 삭제해야하는데, 운영체제가 이를 알 수 없다. LFU도 마찬가지다. 왜냐, 이미 메모리에 올라와있는 경우에는 CPU가 운영체제로 넘어오지 않기 때문에 언제 참조 했는지 운영체제는 알 길이 없다.
- 페이지가 이미 메모리에 존재하는 경우 참조 시각등의 정보를 운영체제가 알 수 없음
- 주소 변환시 이미 물리적인 메모리에 page가 올라간 경우 운영체제가 할 수 있는 게 없음
- O(1)인 LRU의 list 조작 조차 불가능
운영체제가 알 수 있는 정보는 반쪽짜리이다. disk에서 올라온 page의 정보만 알 수 있고 이미 memory에 올라와있는 page가 언제 호출되고 얼마나 호출되었는지는 알 수 없다.
따라서 LRU, LFU는 paging system에서 사용될 수 없다.
Clock Algorithm
LRU의 근사 알고리즘으로 Second chance algorithm, NUR, NRU(Not Recently Used)
로 불린다.
각각의 사각형이 page들이다. page가 참조되어 사용되면 reference bit을 1로 바꿔 페이지가 참조되었다는 것을 알린다. 이는 운영체제가 하는 것이 아니고 하드웨어가 하는 것이다.
page fault가 나서 운영체제가 어떤 page를 내쫓아야한다면 reference bit을 참조해 bit가 1인 페이지는 0으로 바꾸고 다음 page를 조사한다. 조사할 때 reference bit이 0이라면 쫓아낸다. reference bit이 0이라면 시계바늘이 한바퀴 돌아가는 동안에 참조가 없었다는 이야기, 1이라면 한바퀴 도는 동안 적어도 한번의 참조가 있었음을 의미한다.
LRU와 동일한 효과를 보진 못하지만 어느정도 비슷한 효과는 볼 수 있당
개선
- reference bit과 modified bit을 함께 사용
- reference bit = 1 : 최근 참조된 페이지
- modified bit = 1 : 최근 변경된 페이지 (I/O를 동반하는 페이지) -> 어떤 페이지가 쫓겨날 때 만약 modified bit이 0이라면 해당 페이지는 메모리로 올라온 이후로 변경되지 않았으므로 동일한 copy가 backing store에 존재함을 알려준다. 1이라면 내용을 수정한 것이므로 backing store에 수정된 내용을 반영한 다음 지워야한다. => 즉 1일 경우 더 힘이 많이 드니까 최대한 쫓아내지 않는다.
Page Frame의 Allocation
프로그램이 잘 실행되려면 일련의 page들이 메모리에 같이 올라와있어야한다.
메모리 참조 명령어 수행시 명령어, 데이터 등 여러 ㅔ이지 동시 참조
- 명령어 수행을 위해 최소한 할당되어야 하는 frame의 수가 있다.
예를 들어 instruction을 실행함에 있어서 loop를 돌고 있을 때 for문에 속하는 page를 한꺼번에 allocate 되면 loop를 도는 동안 page fault가 나지 않는다. 최소한의 allocation이 없으면 매 loop마다 page fault가 난다.
Allocation : 각각의 프로그램에게 어느정도의 메모리 페이지를 나누어줘 page fault를 줄이는 것
- equal allocation: 모든 프로세스에 똑같은 개수 할당
- proportional allocation: 프로세스 크기에 비례해 할당
- priority allocator: 프로세스의 priority에 따라 다르게 할당
replacement 알고리즘을 사용하다보면
어떤 프로그램이 메모리를 많이 필요로 하면 그 순간에는 많이 올라오고 -> 다른 프로그램의 입지가 좁아진다.
Global Replacement
각 프로그램마다 미리 메모리 할당 X replacement 알고리즘에 따라 할당
replace시 다른 프로세스에 할당된 frame을 빼앗아 올 수 있다.
프로세스 별 할당량을 조절하는 또다른 방법이다.
FIFO, LRU, LFU등의 알고리즘을 global replacement로 사용시에 해당
Working set, PFF 알고리즘 사용
Local Replacement
각 프로그램마다 미리 메모리 할당
자신에게 할당된 frame 내에서만 replacement -> 페이지를 쫓아낼 때 자신에게 할당된 frame중 쫓아냄
FIFO, LRU, LFU 등의 알고리즘을 process 별로 운영시
Thrashing
프로세스의 원할한 수행에 필요한 최소한의 page frame 수를 할당받지 못한 경우
어떤 프로그램에 최소한의 메모리가 할당되지 못하면 page fault가 많이 나는 경우
degree of multiprogramming : 메모리에 올라와있는 프로그램의 개수
CPU utilization이 프로그램이 적을 땐 낮다 -> 프로그램이 I/O하러 갈때 쉬기 때문
프로그램의 수가 오를 수록 I/O 작업을 다른 프로그램이 하러가더라도 일을 할 프로그램이 있기 때문에 CPU Utilization이 높아진다. 하지만 어느 순간 갑자기 낮아지는 것을 볼 수 있는데, 이때 thrashing이 발생한 것이다. page fault가 계속 나 CPU가 I/O 작업을 계속 하러 가야되기때문이다.
이렇게 되면 운영체제는 multiprogramming degree를 높여야 된다고 판단 -> 프로그램이 추가 -> 프로세스당 할당된 frame 수가 더 감소 -> page fault 증가
이걸 막기 위해선 degree of multiprogramming를 조절해줘야한다. 그래서 프로그램이 어느정도는 메모리확보를 할 수 있게 해줘야한다.
Working Set Model
Locality of reference
- 프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조한다.
- loop를 도는 동안엔 loop 내의 요소만 집중적으로 참조, 함수가 실행되는 동안엔 함수 내의 요소를 집중적으로 참조
- 집중적으로 참조되는 해당 page들의 집합을 locality set이라 한다.
Working-Set Model
- Locality에 기반해 프로세스가 일정 시간 동안 원할하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 page들의 집합을 working set이라 정의한다.
- working set 모델에서는 process의 working set 전체가 메모리에 올라와 있어야 수행되고 그렇지 않을 경우 모든 frame을 반납한 후 swap out
- 필요한 모든 데이터를 받을 때 까지 모든 frame을 반납 (안받음)-> suspend
- thrashing 방지
- multiprogramming degree를 결정
결정
동시에 메모리에 올라가면 좋은 page의 집합을 미리 알 수 없으므로 과거를 통해 추측한다. 델타가 10이라고 가정
working set은 계속 바뀔 수 있다. 위의 그림에서도 첫번째 working set에서는 1,2,5,6,7 5개가 필요했으나 두번째 working set에서는 3,4 두개의 페이지만 할당하면 working set을 만족하는 것을 볼 수 있다. 현재 부터 과거 window 크기 델타 이내에 들어오는 페이지들을 working set으로 만들어 메모리에 유지를 시킨다는 것이 working set의 방식이다.
즉, 참조된 후 델타 시간동안 해당 page를 메모리에 유지한 후 버린다.
프로세스들의 working set size의 합 > page frame 수
- 일부 프로세스를 swap out시켜 남은 프로세스의 working set을 우선적으로 충족 시켜 준다.
- MPD를 줄임
Working set을 다 할당하고도 page frame이 남는 경우 - swap out 되었던 프로세스에게 working set을 할당
- MPD를 키움
PFF (Page - Fault Frequency) Scheme
이 방식은 working set 알고리즘 처럼 working set을 추정하는 것이 아니라 직접 page fault rate를 보는 것이다. 현재 시점에서 page fault가 얼마나 나는지 보고, 특정 프로그램이 page fault를 얼마나 내는지 본다.
어떤 프로그램이 page fault를 많이 냄 -> working set이 메모리에 보장이 안되어있음 -> page를 더 줌
일반적으로 프로그램에게 할당되는 메모리 크기가 커지게 되면 page fault가 ㅅ발생하는 비율은 줄게 된다. 하지만 프로그램의 상태에 따라 가파른 정도는 다르다. 하지만 page fault rate이 일정 수준 이상이라면 빈번히 일어난다는 것이다. 그러면 frame을 늘려 page fault를 줄인다. page fault rate가 너무 낮다면 필요한 것에 비해 frame이 많이 할당된 것이므로 frame의 수를 줄인다. 만약 빈 frame이 없어 줄 수 없다면 일부 프로세스를 swap out해 남아 있는 프로그램이라도 page fault rate를 유지해 thrashing을 방지하는 것이다.
Page Size의 결정
paging system에선 동일한 크기의 페이지로 나누게 된다. page size는 보통 4KB를 사용하고 있다.
메모리 주소체계가 32 bit에서 64bit로 바뀌고 메모리 크기도 점점 커지기 때문에 페이지 크기가 너무 작으면 페이지 테이블이 너무 커져 메모리 낭비가 심하다.
메모리 크기 증가 -> page size의 크기를 증가해줄 필요가 있음 -> 최근엔 대용량 페이지 사이즈를 사용하는 이야기도 나오고 있는 추세이다.
Page size를 감소 시키면
- 페이지 수 증가
- 페이지 테이블 크기 증가 -> 메모리 낭비 심해짐
- Internal fragmentation 감소
- Disk transfer 효율성 감소
- 디스크는 원판이 회전하면서 Seek를 해야하는데, 특정 위치에 가서 sector를 읽거나 해야한다.
- 따라서 가능하면 한번 디스크 헤드가 이동해 많은 양의 뭉치를 메모리에 올리는 것이 좋다.
- 페이지가 작으면 seek 횟수가 많아진다. 하지만 seek시간이 오래걸리므로 좋지 않다.
- 필요한 정보만 메모리에 올라와 메모리 이용이 효율적이다.
- 페이지 크기가 크면 해당 페이지 내에서 정말 일부분만 필요함에도 페이지 전체를 올려야 하기 때문에 비효율적이라는 것이다.
- Locality 활용 측면에서는 좋지 않다.
- 함수가 실행되면 함수를 구성하는 코드들이 연달아서 참조가 되기 때문에 page fault가 났을 때 하나로 통째로 올려놓으면 더이상의 함수가 실행되는 동안 더이상의 page fault가 일어나지 않을 것이다.
출처
Operating System Concepts 10th
KOCW 강의 - [운영체제] 이화여자대학교 반효경 교수
