Jun 개발노트

운영체제 09

2020-03-14

가상메모리

  • 정의 : 메인메모리의 원래 용량보다 더 큰 프로세스를 실행시키는 것
  • 방법 : 페이징 된 프로세스 중 필수적인 페이지만 올려(preparing) 실행시켜 프로세스가 실행되는 것처럼 보이는것
  • 추가적인 사항(하드웨어) : valid 비트가 추가된 페이징 테이블

1. 유효 접근 시간

  • cpu가 원하는 페이지를 접근 시간을 평균으로 구한 시간
  • 수식 : Teff = (1-p)Tm + pTp
    • Tm = 해당 페이지를 메모리를 읽는 시간(요청하는 페이지가 메모리에 있음)
    • Tp = 페이지 fault가 일어나 다시 불러와서 읽는 시간(요청하는 페이지가 초기에 메모리에 없음)

2. 지역성의 원리

  • Locality of reference
    • 메모리 접근은 시간적, 공간적 지역성을 가진다.(cpu가 참조하는 주소는 지역성을 가진다(한곳에 모여있다/ 그부분에 있다))
      • 시간적 지역성 : 컴퓨터는 반복문이 많다. 그 부분을 계속해서 읽는다(시간이 지나도)
      • 공간적 지역성 : 1000 주소를 읽었으면, 다음은 1004를 읽듯이 지역성을 가진다. 페이지 fault가 일어나도 블락단위로 가져와서 추후에는 안 유효접근시간이 낮다

페이지 교체

  • Demand Paging
    • 요구되어지는 페이지만 backing store 에서 가져온다.
    • 프로그램 실행 계속에 따라 요구 페이지가 늘어나고, 언젠가는 메모리(Memory full)가 가득 차게 된다.
  • Memory full!
    • 메모리가 가득 차면 추가로 페이지를 가져오기 위해
    • 어떤 페이지는 backing store 로 몰아내고 (page-out) / 그 빈 공간으로 페이지를 가져온다 (page-in)
  • victim page : 어떤 페이지가 page-out 될것인가
    • 선택조건 : 수정되지 않는 페이지(단순 명령 및 읽는 페이지)를 victim으로 선택
    • 추가사항 : 페이징 테이블에 modified bit(수정하는 페이지인가 여부)를 추가해서 확인
    • 여러가지 victim page 중에 어떤 페이지가 나가야 할것인가?
      • Random
      • FIFO
      • 페이지 교체 알고리즘

1. Page reference string

  • CPU 가 내는 주소: 100 101 102 432 612 103 104 611 612
  • Page size = 100 바이트라면
  • 페이지 번호 = 1 1 1 4 6 1 1 6 6
  • Page reference string = 1 4 6 1 6 ('1'페이지가 처음에 페이지 fault가 일어나면 그 이후는 지역성때문에 안 읽어난다.)

2. Page Replacement algorithms

  • FIFO(First-in-first-out)

    • Simplest
      • Idea: 초기화 코드는 더 이상 사용되지 않을 것
    • 예제
      • 페이지 참조열 = 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
      • number of frames = 3 (메모리의 크기)
      • 15 page faults
    • 이상현상
      • 메모리 용량이 증가하면 PF 회수 증가(통계적으로)
  • OPT(OPtional)

    • 규칙 : 한번만 사용될 페이지 / 자주 사용안되는 페이지를 교체대상으로 하자
    • 예제
      • 페이지 참조열 = 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
      • number of frames = 3 (메모리의 크기)
      • 9 page faults
    • 비현실적이다 적용하기 어렵다
      • 이유 : 미래를 알 수 없다( == SJF scheduling algorithm)
  • LRU(Least-Recently Used)

    • 규칙 : 최근에 사용되지 않으면 나중에도 사용되는 않은 것 같은 페이지를 victim page로 선택
    • 예제
      • 페이지 참조열 = 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
      • number of frames = 3 (메모리의 크기)
      • 12 page faults
    • 대부분의 컴퓨터는 LRU알고리즘 사용한다.

3. Global vs Local Replacement

  1. Global replacement
    • 메모리 상의 모든 프로세스룰 대상으로 교체 후보로 정한다.
  2. Local replacement
    • 메모리 상의 해당 프로세스를 대상으로 교체 후보에 정한다.
  3. 성능비교
    • 글로벌이 더 효율적이다(통계상으로)

프레임 할당

  1. 쓰레싱(Thrashing) 쓰레싱
    • CPU utilization(cpu 활용률) vs Degree of multiprogramming(메인메모리에 올라온 프로세스 갯수)
      • 프로세스 개수 증가 > CPU 이용률 증가
      • 일정 범위를 넘어서면 CPU 이용률 감소
      • 이유: 빈번한 page in/out – Thrashing: i/o 시간 증가 때문
      • i/o : 디스크에서 해당 프로세스 페이지를 찾고 올리고 하는 작업
    • Thrashing 극복
      • Global replacement 보다는 local replacement
      • 프로세스 당 충분한/적절한 수의 메모리(프레임) 할당
  2. 프레임 할당
    • 정적할당 (비효율적이다)
      • 균등할당 : 크기를 고려하지 않고 프로세스당 동일한 프레임를 할당
      • 비례할당 : 전체 프레임수를 해당 프로세스의 크기 별로 비례하여 할당
    • 동적할당 (실제로 사용)
      • Working set model
      • Page faults frequency
      • etc