운영체제 - 08

강의

http://www.kocw.net/home/search/kemView.do?kemId=1226304

운영체제 - 가상메모리

• 아래는 모두 paging 기법을 사용한다고 가정한다.

1. Demand Paging

• 실제로 필요할 때 page를 메모리에 올리는 것
• I/O양의 감소
• 메모리 사용량 감소
• 빠른 응답 시간
• 더 많은 사용자 수용

valid / Invalid bit의 수용

• Invalid의 의미 : 사용되지 않는 주소 영역인 경우, 페이지가 물리적 메모리에 없는 경우
• 처음에는 모든 페이지 엔트리가 invalid로 초기화
• 주소 번역시에 invalid bit가 set되어 있으면 page fault

• 맨 왼쪽은 프로세스가 물리적 메모리 올라가기전 컴파일된 로지컬 메모리
• 왼쪽 두번째는 페이지 테이블
• 세번째는 실제 프로세스가 올라가는 물리적 메모리
• 맨 오른쪽은 스왑영역. 물리적 메모리에서 나간 프로세스들이 대기하는 장소
• 예를들어 B 프로세스가 실행하기 위해 자기 번호와 맵핑된 페이지 테이블 1번 봤는데 invalid bit가 1이여서 page fault가 발생-> 운영체제에게 권한이 넘어감

2. Page Fault

• invalid page를 접근하면서 MMU가 trapㅇ을 발생시킴(page fault trap)

• 커널 모르로 들어가서 page fault handler가 invoke됨

• 다음 과 같은 순서로 처리

  

  1. bad address, protection violation을 위해 invalid reference(유효하지 않는 참조,접근)이면 abort process(프로세스 중지)한다.
  2. Get an empty page frame(여유 메모리가 없으면) -> page replacement (다른 프로세스 내보내고 들어가야한다)
  3. 해당 페이지를 disk(그림에서 원통 모양)에서 메모리로 읽어온다.
     1. disk I/O가 끝나기까지 이 프로세스는 CPU를 선점당함 (block)
     2. 디스크 read가 끝나면 page tables 엔트리 기록, valid/invalid bit를 valid로 변경
     3. 대기 큐에 프로세스를 넣는다. -> dispatch later
  4. 이 프로세스가 CPU를 잡고 다시 실행
  5. 아까 중단되었던 instruntion을 재개

2.1 Free frame이 없는 경우

2.1.1 Page replacement

• 어떤 frame을 빼앗아올지 결정해야 함
• 곧바로 사용되지 않을 page를 쫒아내는 것이 좋음
• 동일한 페이지가 여러 번 메모리에서 쫒겨났다가 다시 들어 올 수 있음

2.1.2 Replacement 알고리즘

• 페이지 fault rate를 최소화하는 것이 목표
• 알고리즘 평가 page reference string에 대해 page fault를 얼마나 내는지 조사
• reference string의 예 : 1,2,3,4,1,2,5,1,2,3,4,5

2.2 Optimal 알고리즘

• MIN(OPT) : 가장 먼 미래에 참조되는 페이지를 replace
• 미래를 안다고 가정하고 아래 예시

• 중간에 7번째의 5가 참조될때 4를 내쫒음. 이유는 그 이후 프레임에 있는 1,2,3,4 중 4가 가장 나중에 page가 참조되므로 내쫒음.

• 미래의 옵티말 알고리즘? : 사실상 미래를 알 수가 없음. 그래서 현실에선 사용하지 않음. 가장 이상적인 알고리즘일뿐. 그래서 오프라인 알고리즘이라고 부름.
• 다른 알고리즘의 성능에 대한 upper bound제공: Belady’s 옵티말 알고리즘, MIN, OPT등으로 불림

2.2 FIFO(First In First Out) 알고리즘

• 먼저 들어온 것 먼저 내쫒음

• FIFO anomaly(변칙) : 프레임이 많을 수록 페이지 fault가 많이 발생

2.3 LRU(Least Recently Used) 알고리즘

• 가장 오래 전에 참조 된 것을 지움
• 모든 프레임을 다 탐색해야 함(링크드리스트). 비효율적

2.4 LFU (Least Frequently Used) 알고리즘

• 참조 횟수가 가장 적은 페이지를 지움
• 장기적인 시간 규모를 보기 때문에 page 인기도를 잘 반영한다.
• 앞으로 참조가 많을 페이지를 반영하지 못함.
• 구현이 복잡함

** 다양한 캐슁 환경

• 캐슁 기법 : 빠른 속도의 공간에 요청된 데이터를 저장해 두었다고 후속 요청시 캐쉬로부터 직접 서비스하는 방식.
• 페이징 시스템 외에도 캐쉬 메모리, 버퍼 캐슁, 웹 캐싱에 사용

** 캐쉬 운영의 시간 제약

• 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리느 ㄴ경우 실제 시스템에서 사용할 수 없음.
• 버퍼 캐슁이나 웹 캐슁의 경우 : O(1)에서 O(long N) 정도까지 허용
• 페이징 시스템의 경우 : 페이지 fault인 경우만 OS가 관여함. 페이지가 이미 메모리에 존재하는 경우 OS가 알 수 없음. O(1)인 LRU의 list 조작조차 불가능
• 왜냐하면 일단, OS는 로지컬 주소에서 물리적 주소로 변환할때 개입이 없다. 이것은 하드웨어가 함.
• 그 후 만약 물리적 주소에 없어서 page fault가 난다면 그때는 디스크에서 물리적 주소로 가져와야 한다. 이때 OS가 껴들어서 LRU, LFU 알고리즘을 토대로 물리적 주소에 옮기고 페이지 테이블에 대한 정보를 최신화 시킨다.(LRU의 경우 list에 넣거나, LFU인 경우 Heap을 최신화)
• 그런데 이미 해당 페이지가 물리적 주소에 있는 경우. 즉, 유효한 경우일 때는 OS가 참견할 일이 없다. 이러면은 LRU나 LFU 알고리즘을 최신화할 틈이 없음. 이것은 OS가 해야하므로. 그래서 실제로는 쓰이지 않는다.

2.6 Clock 알고리즘

• 실제 사용하는 알고리즘

• LUR 알고리즘과 유사함
• Second Chance 알고리즘, NUR(Not Used Recently) 또는 NRU(Not Recently Used)라고 불림.
• Reference bit를 사용해서 교체 대상 페이지를 선정(원형 리스트)
• 최근에 표시 된 페이지는 1, 아닌 페이지는 0
• 레퍼런스 비트가 0인 것을 찾는다.
• 찾으면서 1인 페이지를 0으로 바꾼다.
• 0인 것을 찾으면 페이지를 교체
• 자주 사용되는 페이지이면 그대로 1을 유지

2.6.1 clock 알고리즘 개선

• reference bit와 modified bit를 함께 사용
• reference bit 최근 참조된 페이지
• modified bit 최근 변경된 페이지

2.7 페이지 프레임 할당

• 각 프로세스에 얼마만큼의 페이지 프레임을 할당할 것인가?
• 메모리 참조 명령어 수행시 명령어, 데이터 등 여러 페이지 동시 참조
• loop를 구성하는 페이지들은 한꺼번에 할당 되는 것이 유리
  • 최소한의 할당이 없으면 loop 실행될 때마다 page fault가 발생
• 종류
  1. Equal 할당 : 모든 프로세스에게 똑같은 갯수 할당
  2. Proportional 할당 : 프로세스 크기 비례하여 할당
  3. Priority 할당 : 프로세스의 우선순위따라 할당

2.8 Global vs Local replacement

2.8.1 Global

• replace시 다른 프로세스에 할당된 frame을 빼앗아 올 수 있다.
• FIFO, LRU, LFU 알고리즘을 global로 사용할 때 해당
• Working set, PFF 알고리즘 사용
• 특정 프로세스가 메모리를 독식할 수 있음

2.8.2 Local

• 자신에게 할당된 frame만 할당됨
• FIFO, LRU, LFU 등의 알고리즘을 프로세스 별로 운영시

2.9 Thrashing

• 프로세스의 원활한 수행에 필요한 최소한의 page frame 수를 할당 받지 못한 경우 발생
• 너무 많은 프로그램이 실행되면 발생
• Page fault rate 매우 높아짐
• CPU 이용률 낮아짐
• OS는 CPU가 놀고 있으니 프로세스를 더 실행. 즉, MPD(Multiprogramming degree)를 높여야 한다고 판단
• 또 다른 프로세스가 시스템에 추가됨
• 프로세스 당 할당된 frame의 수가 더욱 감소
• 프로세스는 page의 swap으로 매우 바쁨
• 대부분의 시간에 CPU는 한가함
• 낮은 성능
• 이를 방지하기 위해 working set 알고리즘, PFF 알고리즘이 있음

2.10 Working-Set Model (알고리즘)

2.10.1 Locality of reference

• 프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조한다.
• 집중적으로 참조되는 해당 page들의 집합을 locality set이라 함

2.10.2 Working-set Model

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

2.11 PFF(Page Fault Frequency) Scheme (알고리즘)

• page-falut rate의 상한값과 하한값을 둔다.
• 상한 값이 넘으면 frame을 더 할당
• 하한 값을 이하면 frame 수를 줄인다.
• 빈 frame이 없으면 swap out

2.12 Page 사이즈 결정

• 감소시키면
  • 페이지 수 증가
  • 테이블 크기 증가
  • 내부 조각 감소
  • 디스크 번역 효율성 감소
  • 필요한 정보만 올라오기에 메모리 이용 효율적
• 그러나 요즘은 큰 사이즈로 하는게 대세