[운영체제] 가상 메모리 2 : Clock Algorithm, Page frame allocation, Thrashing

가상 메모리 1 내용과 이어집니다
(참고 강의 : http://www.kocw.net/home/search/kemView.do?kemId=1046323)

다양한 캐싱 환경 (caching)

캐싱 기법

• 한정되고 빠른 공간(=캐시)에 요청된 데이터를 저장해두었다가 후속 요청시 캐시로부터 직접 서비스 하는 방식
• Paging system, cache memory, buffer caching, Web caching 등 다양한 분야에서 사용

캐시(Cache)가 저장한다는 뜻이다.
자주 쓰는 데이터를 한정되고, 빠른 공간에서 가져다 씀으로서 속도를 높이는 기술이다.

캐시 운영의 시간 제약

• 교체 알고리즘에서 삭제할 항목을 결정하는 일에 많은 시간을 쓰면 실제 시스템에서 사용할 수 없음
• Buffer caching, Web caching : O(1) ~ O(log n)정도 까지 허용
• **Paging system
  - page fault 경우에만 OS가 관여함
  -페이지가 이미 메모리에 존재하는 경우 참조시각 등의 정보를 OS가 알 수 없음
  -O(1)인 LRU인 list 조작조차 불가능

**앞서 교체 알고리즘으로 FIFO, LRU, LFU를 배웠는데, 실제로 컴퓨터에 적용할 수가 없다.
그 이유는 운영체제가 page fault일 경우에만 관여를 하기 때문이다.
LRU, LFU 모두 정보가 운영체제 저장이 되는데,
page fault가 일어나기 전까지는 하드웨어가 전부 알아서 한다.
page fault가 일어나서야 운영체제가 일을 하는데,
그 전까지 발생했던 페이지들 요청 순서, 참조 빈도를 어떻게 알겠는가?

결론적으로

Paging system에서 LRU,LFU는 사용할 수 없다. 불가능하다.

그럼 어떤 알고리즘 써야 하냐고?

Clock Algorithm

• LRU의 근사 알고리즘
• second chance 알고리즘, NUR(Not Used Recently), NRU(Not Recently Used)라고도 불림
• Reference bit을 이용해 교체 대상 페이지 선정 (circular list)
• Reference bit이 0인거 찾을 때 까지 포인터 이동
• 포인터 이동 중 reference bit 1은 전부 0으로 바꿈
• Reference bit 0인거 발견하면 그 페이지 교체
• 한 바퀴 돌아와서도(=second chance) 0이면 그 때 replace 당함
• 자주 사용되는 페이지라면 second chance 올 때 1

뭔 소린지 글만 읽어선 감이 안 온다.

OS는 평소에는 무슨 일이 일어나는지 모르니 하드웨어가 reference bit을 기록해준다.
page마다 사용했으면 1로 바꿔주는 것이다. 기본은 0일 것이고.

page fault가 발생해 OS가 일어났는데 메모리가 꽉 찼어? 그럼 어떤 걸 지울지 정할 때 circular list를 활용하는 것이다.
시계방향으로 하나씩 보면서 1인 페이지는 0으로 바꾸고 넘어간다. (1이라는 건 최근에 사용했다는 뜻이니까)
그러다 0을 만나면 걔를 버리는 것이다. (0이라는 건 최근에 안 썼다는 거니까)

개선된 Clock Algorithm

• reference bit + Modified bit(dirty bit) 함께 사용
• reference bit = 1 : 최근에 참조한 페이지
• modified bit = 1 : 최근에 변경된 페이지 (I/O 동반하는 페이지)

Modified bit(dirty bit)을 활용해 이전 포스팅에서 봤던,
메모리에서 Swap out을 할 때 디스크에 옮겨야 할지, 그냥 버려야 할지 정할 수 있는 것이다.
(페이지가 read-only라면 디스크랑 메모리랑 똑같은 값인데 뭣하러 옮겨, 그냥 메모리만 지우면 되지)

Page frame allocation

각 프로세스마다 얼만큼의 page frame을 할당할 것인가? (프로세스마다 얼마나 메모리를 줄 것인가)

Allocation의 필요성

• 메모리 참조 명령어 수행 시 명령어, 데이터 등 여러 페이지 동시 참조
  - 명령어 수행 위해 최소한 할당되어야 하는 frame 수가 있음
• Loop 구성하는 page들은 한 꺼번에 allocate 되는 것이 유리함
  - 최소한의 allocation이 없으면 매 loop 마다 page fault 일어날테니
  

실행 파일의 0번 째 줄을 보자. 저 한 줄 명령어를 실행하는데는 20, 30 번지 코드가 반드시 필요하다.
즉 최소 3개 page frame은 있어야 명령어 수행이 가능하다는 것이다.
반복문도 마찬가지다. 한 loop 안에 있는 페이지들을 물리적 메모리에 올려놔줘야 원할히 돌아가지
반복문 계속 돌아갈 때 마다 page fault 내고 ㅈㄴ 느려지게 하는게 맞냐?

대부분의 프로세스의 경우 그럴 것이다.

프로세스 당 최소 몇 개의 page frame이 있어야 시스템 전체적으로 최적화를 할 수 있을까?

에 대한 고민이라고 여겨보자.

Allocation Scheme

• Equal allocation : 모든 프로세스에 똑같은 개수 할당
• Proportional allocation : 프로세스 크기에 비례하여 할당
• Priority allocation : 프로세스 priority에 따라 다르게 할당

Global vs Local Replacement

남의 것을 뺏을 수 있냐? 내 영역 내에서 바꿔야 하냐 ? 차이이다

Global replacement

남(다른 프로세스)의 땅(frame)을 뺏는게 가능하다는 것이다.

• Replace 시 다른 process에 할당된 frame을 뺏을 수 있다.
• Process 별 할당량을 조절하는 또 다른 방법
• FIFO, LRU, LFU 등의 알고리즘을 global replacement로 사용시에 할당
• Working set, PFF 알고리즘 사용

Local replacement

내가 가진 프레임 내에서 교체를 해야된다는 것이다.
남의 땅 못 뺏고 내 땅 내에서 뭘 교체할 지 정해야 한다.

• FIFO, LRU, LFU 등의 알고리즘을 process 별로 운영시
• 자신에게 할당된 frame 내에서만 replacement

실제 컴퓨터에서 둘 다 사용가능하다고 한다.

Thrashing

• 프로세스의 원활한 수행해 필요한 최소한의 page frame 수를 할당받지 못한 경우 발생
• Page fault rate이 매우 높아짐
• CPU Utilization 낮아짐
• OS는 MPD(Multi Programming Degree)를 높여야 한다고 판단
• 또 다른 프로세스가 시스템에 추가됨
• 프로세스 당 할당된 frame 수 더 감소
• 프로세스는 page swap in / out 으로 매우 바쁨 (OS가 함)
• 대부분 시간에 CPU는 한가함
• low throughput

(여기서 말하는 CPU Utilization은 CPU가 프로그램 실행에 얼마나 힘을 쏟느냐 정도로 생각하자. OS 작업에서 CPU 안쓰냐? 다 CPU가 한다.)

CPU 코어가 1개라고 가정하고,
프로세스가 늘어날수록 CPU Utilization는 커진다.
context switching하면서 열심히 하시잖아.
근데 어느 순간 확 준다. 왜?

프로세스가 ㅈㄴ 많아서 메모리에 자리가 부족하니까, 툭 하면 page fault 날테고, OS가 열심히 일하시잖아.
실제로 프로그램 실행을 위해 CPU를 쓰는게 아니라, OS가 다 해쳐먹고 있는 상황이 되는것이다.

그럼 CPU Utilization을 가장 잘 활용하려면 어떻게 해야 할까?

1. Working-Set Model

Locality of reference

• 프로세스는 특정 시간 동안 일정 장소만 집중적으로 참조하는 특성이 있더라
• 집중적으로 참조되는 해당 page 집합을 locality set이라 함

Working-set Model

• Locality에 기반하여 프로세스가 일정 시간동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 page 집합을 Working Set이라함
• Working set 모델에서는 process의 working set 전체가 메모리에 올라와 있어야 수행되고 그렇지 않을 경우
  모든 frame 반납 후 swap out
• Thrashing 방지함
• Multiprogramming degree를 조절

근데 Working set을 어떻게 알아내고 결정할 것인가?
그것을 알고리즘을 통해 정한다.

Working-Set Algorithm

Working set 결정

2. PFF(Page Fault Frequency) Scheme

프로세스마다 page-fault rate를 체크해서, 너무 많이 일어나면 frame을 더 주고, 아니면 좀 줄이고 한다.

Page 사이즈 결정

페이지 사이즈 작아지면

• 페이지 수 증가
• 페이지 테이블 크기 증가
• Internal fragmentation 감소
• Disk transfer 효율성 감소
• 필요한 정보만 메모리에 올라와 메모리 이용이 효율적

트렌드 : 사이즈 키워!