8장 가상 메모리 - 운영체제와 정보기술의 원리

🦊 가상 메모리 : 프로세스 입장에서 자신만의 메모리라고 생각하는 0번지부터 시작되는 메모리 공간

• 장점: CPU가 실행할 부분만 물리적 메모리에 로딩하고 나머지는 스왑영역에 내려놓는다.
• 프로세스가 필요로하는 메모리가 컴퓨터의 물리적 메모리보다 커도 실행할 수 있다.

🦊 가상 메모리의 기법

• 요구 페이징과 요구 세그먼테이션으로 나뉘는데 대부분 요구 페이징 기법을 쓴다.
• 요구 세그먼테이션 기법조차도 세그먼트를 페이지로 나뉘는 페이지드 세그먼테이션 기법을 쓰기 때문에 세부적으로 봤을때 전부 페이징 기법을 쓴다.

🦊 요구 페이징 기법

• 프로세스는 페이지 단위로 나누고 메모리는 프레임 단위로 나눠서 실행에 필요한 페이지만 메모리에 적재함
• 메모리 사용량 ⬇, 메모리에 올리는데 사용되는 오버헤드 ⬇
• 위에서 언급했지만 필요한 페이지만 메모리에 올리므로 프로세스가 필요로 하는 메모리가 물리적 메모리보다 커도 상관없음

🦊 유효-무효 비트(valid-invalid bit)

• 프로세스 실행전 전부 무효로 세팅
• 특정 페이지가 참조되어 메모리에 올라가면 유효로 세팅
• 스왑 영역으로 쫓겨나면 다시 무효로 세팅
  즉 유효-무효비트가 무효 => 페이지가 현재 메모리에 올라와 있지 않음 or 프로세스 실행 전

🦊 페이지 부재

• 페이지 참조시 유효-무효비트가 무효인 경우

🦊 페이지 부재시 처리 과정

1. CPU가 무효 페이지에 접근
2. 주소 변환 담당 하드웨어 MMU가 페이지 부재 트랩(page fault trap)을 발생시킴
3. CPU의 제어권이 커널모드로 전환
4. 운영체제의 페이지 부재 처리루틴(page fault handler)가 호출됨
5. 해당 페이지에 대한 접근이 적법한지 운영체제가 검사
6. 사용되지 않는 주소 혹은 접근 권한 위반(protection violation)의 경우 해당 프로세스 종료
7. 적법한 경우 물리적 메모리에 비어있는 프레임(free frame)을 할당받아 페이지를 읽음
8. 비어있는 페이지가 없는 경우 메모리에 올라와 있는 페이지 중 하나를 스왑아웃 시킴
9. 요청된 페이지를 디스크로부터 메모리로 적재할때까지 오랜 시간이 걸리므로 그동안 페이지 부재를 발생시킨 프로세스는 봉쇄 상태
10. 봉쇄 상태 들어가기 전 CPU 레지스터 상태 및 프로그램 카운터값을 프로세스 제어블록에 저장해둠
11. 디스크 입출력이 완료되면 인터럽트 발생
12. 페이지 테이블에서 해당 페이지의 유효-무효 비트를 유효로 설정
13. 봉쇄 되었던 프로세스는 준비 큐로 이동
14. 준비 큐에 있다가 CPU를 할당받게 되면 중단되었던 명령부터 실행

🦊 요구 페이지의 성능

• 페이지 부재시 디스크로부터 페이지를 읽는데 막대한 오버헤드가 발생
• 페이지 부재가 최대한 적게 발생해야 성능을 올릴 수 있음
• 요구 페이지의 성능 계산식
  
  P = 페이지 부재 발생비율(page fault rate)

🦊 페이지 교체 과정

• 페이지 교체 알고리즘
  • 페이지 부재시 빈 페이지마저 없어 어떤 페이지를 스왑 아웃 시킬지 결정하는 알고리즘

🦊 페이지 교체 알고리즘의 성능

• 주어진 페이지 참조열(Page Reference String)에 대해 페이지 부재율을 계산함
• 페이지 참조열: 참조가 요구되는 페이지들의 나열

🦊 페이지 교체 알고리즘 종류

1. 최적 페이지 교체(발레디의 최적 알고리즘, MIN, OPT등으로 불림)

• 가장 먼 미래에 참조될 페이지를 쫓아냄
• 이게 제일 빠르지만 실제 시스템에서 온라인으로 사용할 수 있는 알고리즘이 아님
• 이보다 빠를 수 없어서 이 알고리즘의 성능과 비슷할수록 좋은 알고리즘으로 평가됨
  

2. 선입선출 알고리즘

• 먼저 참조되었던 메모리부터 방출
• 향후 참조 가능성을 고려하지 않음
• 성능이 안좋음
• 프레임이 늘어난다고 페이지 부재가 줄어들지 않을수도 있음(늘어나기도 함)
• 위 현상을 FIFO의 이상현상(FIFO anomaly)라고 함
  

3. LRU 알고리즘(Least Recently Used)

• 최근의 참조된 페이지가 가까운 미래에 또 참조될 가능성이 크다는 전제를 바탕으로 한 알고리즘
• 즉 가장 오래전에 참조된 페이지를 쫓아냄
  

4. LFU 알고리즘(Least Frequently Used)

• 참조횟수(Reference Count)가 적었던 페이지부터 방출
• 참조횟수가 같은 경우 임의로 하나를 선정하는데 이때는 보통 오래전에 참조된 페이지를 쫓아내도록 함
• 참조횟수를 계산하는 방식 => Incache-LFU, Perfect-LFU
  • Incache-LFU
    • 방출됐다가 다시 들어온 경우 참조 횟수가 1로 초기화됨
  • Perfect-LFU
    • 쫓겨나도 참조 횟수가 초기화 되지 않음
    • 오래 기억하고 있어야 돼서 오버헤드가 더 큼

LRU와 LFU의 장단점

LRU는 과거의 기록을 반영하지 못하지만 오버헤드가 작음
LFU는 과거의 기록을 반영하지만 최신의 일어난 변화에 반응이 덜하고 LRU보다 구현이 복잡함

• 둘의 결과가 극단적으로 다른 예
  

LRU는 O(1)의 복잡도: 링크드 리스트로 구현됨. 참조된것을 찾아서 제일 최신으로 갖다 놓으면 되므로 삭제와 추가에 O(1)만큼만 시간이 걸림

(검색할때는 시간이 걸리지 않는건가? 테이블에서 검색하기 때문에?)

LFU는 링크드 리스트로 구현되면 현재 메모리가 참조돼서 참조횟수가 +1이 된경우 다른 메모리의 횟수와 비교해야 되는데 이때 최악의 경우 O(n)만큼의 시간이 걸림 이 시간을 줄이기 위해 HEAP으로 구현을 하게 되는데 이렇게 되면 O(logN)만큼의 시간이 걸림

LRU와 LFU를 실제로 구현할 수 있는가?

페이지 참조는 운영체제와 상관이 없다. 하드웨어적으로 MMU가 주소를 변화해주기 때문이다.
하지만 페이지 부재가 일어난경우 CPU의 제어권을 사용자 프로그램에서 운영체제에게 이양되고 운영체제가 디스크로부터 부재된 메모리를 가져와서 메모리 프레임에 올려놓는다.
다시 말해 메모리가 페이지 테이블에 존재한다면 운영체제의 개입이 없어서 운영체제는 메모리의 참조 시간과 횟수를 기록할 수 없다.
다만 페이지 부재시에는 CPU 권한이 운영체제로 넘어가기때문에 이 정보만 알수 있지만 구현하는데 너무 부족한 정보이다
즉 페이징 시스템에서 LRU와 LRU는 무용지물이다. (Buffer caching 이나 Web Caching에서는 사용 가능)

5. 클럭 알고리즘

• 위의 알고리즘에서 페이지 프레임이 선형으로 배치된것과 달리 원형 배치되어 있음
• 처음 페이지가 참조될 때 Reference bit을 1로 설정
• 페이지 교체시 교체 대상을 선정할 때 포인터가 프레임의 Reference bit을 원형으로 돌면서 검색함
• 포인터가 Reference Bit에 도착했을 때 1이면 0으로 만드로 0이면 해당 프레임의 페이지를 스왑 아웃시킴
• 포인터가 참조된 이후로 한바퀴는 프레임에 살아 남아있을 수 있어서 Second chance algorithm이라고도 불림. 혹은 NUR(Not Used Recentrly), NRU(Not Recently Used)로 불림

Clock algorithm의 개선

• Modified Bit: 페이지가 메모리로부터 불러온 뒤 메모리에 Write가 일어난 경우 modified bit이 1로 설정되고 나중에 해당 페이지가 스왑 아웃 될때 메모리의 수정된 내용을 디스크에 기록함

  왜 개선인지는 모르겠음

🦊 Allocation Problem

• 각 process에 page frame을 얼만큼 할당할 것인가
• 너무 많이 할당하면 메모리에 동시에 올라간 프로세스가 적어서 일하지 않는 CPU가 생겨서 CPU Utilization(활용도)가 떨어지고
• 너무 조금씩 할당하면 프로세스가 최소로 필요로 하는 frame마저도 충족을 못시킴
  • 예를 들어 프로세스가 반복문을 돌릴 경우 반복문에 필요한 코드는 계속 메모리에 올라와 있어야 하는데 그 중 하나라도 메모리에 없는 경우 페이지 매 반복마다 일어나게됨

🦊 Allocation Scheme

1. Equal Allocation: 모든 프로세스에게 똑같이 할당

2. Proportional Allocation: 프로세스 크기에 비례해서 할당

3. Priority Allocation: 프로세스의 priority에 따라 다르게 할당

🦊 Trashing

🐹 그래프 해석

• 동시에 실행되는 프로세스가 많아질수록(MPD가 커질수록) 초반에는 CPU utilization이 올라감
  • 프로세스가 적으면 해당 CPU사용보다 I/O 작업이 많아서 CPU사용률이 적음
• 프로세스가 많아질수록 프로세스가 I/O작업이어도 준비큐에 있는 다른 프로세스에게 CPU를 할당해서 CPU가 놀고 있는 시간이 적어짐
• 프로세스가 특정 숫자 이상으로 많아지면 한 프로세스에게 할당된 페이지가 너무 적어져서 아주 조금을 돌리기 위해서도 페이지 부재가 발생함
  • 페이지 부재가 발생한 순간 디스크에서 해당 페이지를 불러오는 I/O작업이 일어나고 프로세스는 봉쇄상태가 되어서 다른 프로세스에게 CPU가 이양됨
  • 할당된 페이지가 작아지면 작아질수록 거의 모든 프로세스는 CPU작업은 못하고 페이지를 데려오는 I/O작업만 일어나서 CPU는 아무일을 못해서 이용률이 최악이 됨
  • 아이러니하게 CPU 이용률이 줄어들면 운영체제는 동시의 돌아가는 프로세스가 적다고 판단해서 프로세스를 더 많이 메모리에 올리려고 함.
• 이렇게 CPU사용률이 급격하게 줄어드는 것을 thrashing이라고 함

🦊 Working-Set Model

• 일정 수준의 메모리를 보장해주지 않는다면 프로세스의 모든 frame을 반납(suspend)하고 메모리가 확보될때까지 기다림
  

🦊 Page Size

• 현재 OS의 페이지 사이즈즈 4KB
  
• 메모리가 너무 크다보니 페이지수가 너무 많아짐. 해당 페이지마다 주소를 저장하는 페이지 테이블의 크기가 너무 증가함
• 1개의 페이지가 커진다면 내부조각의 양도 커질것임
• 페이지 부재시 해당 페이지를 스왑영역에서 가져오게 되는데 이때 찾는 시간이 오래걸림. 페이지가 크다면 한번에 메모리에 올라가는 양이 많아지기 때문에(올리는 시간은 상대적으로 적음) 부재가 적게 일어나고 한번에 많이 올려버리는 편이 좋음. 이 관점에서는 Page Size가 큰게 좋음