🍜 배경

• 프로그램 코드는 실행 시에 메모리에 적재되어 있어야 하지만, 전체 프로그램의 사용은 빈번하지 않음 (ex. 에러 코드, 비정상적인 루틴, 대규모 데이터 구조)
• 전체 프로그램 코드가 동시에 필요하지 않음
• 프로그램의 일부만 메모리에 적재하고 실행 시 이점
  • 프로그램이 더 이상 물리 메모리의 크기 제약을 받지 않음
  • 각 프로그램의 실행 시 메모리를 덜 차지함
    • 동시에 더 많은 프로그램의 실행이 가능
    • 응답시간이 증가시키지 않으면서 CPU 활용도의 효율성 증대
  • 프로그램을 메모리로 적재하거나 스왑 시에 더 적은 I/O 필요
    • 각 사용자 프로그램이 더 빨리 실행
• 가상 메모리(virtual memory)는 실제의 물리 메모리 개념과 사룡자의 논리 메모리 개념을 분리
  • 프로그램의 일부분만 메모리에 올려 놓고 실행
  • 물리 주소 공간보다 훨씬 큰 논리 주소 공간(가상 주소 공간)을 제공
  • 여러 프로레스들에게 공유되는 주소 공간을 허용
  • 효율적인 프로세스 생성이 가능
  • 더 많은 프로그램들이 병행 실행 될 수 있음
  • 프로세스 적재 및 스왑 시에 더 적은 I/O 필요
• 가상 메모리 공간(virtual memory space)는 프로세스가 메모리에 저장되는 논리적인 관점
  • 0번지 주소부터 시작되는 연속적인 주소 공간
  • 반면, 물리 메모리는 페이지 프로엠들로 구성
  • 논리주소를 물리주소로 변화 MMU(Memory Management Unit)
• 가상 메모리 구현
  • 요구 페이징 (demand paging)
  • 요구 세그멘테이션 (demand segmentation)

🛶 프로세스의 가상 주소 공간

일반적으로 논리 주소공간의 최대 주소에서 스택이 시작되어 낮은 주소로 확장되고, 힙은 높은 주소 방향으로 확장

• 두 영역 사이에 사용되지 않은 주소 공간은 빈 영역(hole)
  • 힙이나 스택이 새로운 페이지로 확장되기 전에는 물리 메모리가 필요하지 않음
• 확장될 빈 영역의 성긴 주소 공간 (sparse address space)에 동적 연결 라이브러리 등이 배치
• 시스템 라이브러리 등은 가상 주소 공간을 매핑

🐫 가상 메모리를 사용할 때의 공유 라이브러리

🚵 요구 페이징(Demand Paging)

• 프로세스 전체를 메모리에 적재하지 않고, 필요한 페이지만을 물리 메모리에 적재
  • 사용되지 않을 페이지를 메모리에 가져오지 않음으로써 시간 낭비와 메모리 공간 낭비 줄임
  • 입출력 과정 감소
  • 적은 메모리 사용
  • 더 빠른 응답
  • 더 많은 사용자 허용
• 스와핑을 갖는 페이징 시스템과 유사
• 필요한 페이지를 참고
  • 잘못된 참조 → 취소
  • 물리 메모리에 없으면 → 메모리로 가져옴
• 게으른 스와퍼(lazy swapper)
  • 페이지가 필요하지 않으면 메모리 적재하지 않음
  • 페이지를 관리하는 스와퍼를 페이저(pager)라 함

유효-무효 비트 (Valid-Invalid Bit)

• 페이지가 메모리에 올라와 있는지 구별을 위해 페이지 테이블에 유효-무효 비트 표시
  • 유효비트(v, valid)로 세트되면 페이지가 메모리에 있음 표시
  • 무효비트(i, invalid)로 세트되면 페이지가 메모리에 없음 표시
  • 초기에는 i으로 지정
• 주소 변환 중 무표비트 i로 세트되어 있으면 페이지 부재(page fault) 발생
• 일부 페이지들이 메인 메모리 없는 경우 페이지 테이블

페이지 부재 (Page Fault)

• 프로세스가 메모리에 올라와 있지 않은 페이지를 접근하는 경우 페이지 부재(page-fault) 트랩(trap)이 발생
• 페이지 부재 처리 과정
  1. 운영체제는 내부 테이블(PCB와 함께 유지)을 검사하여 메모리 참조가 유효인지 무효인지를 조사
     1. 무효한 참조 → 프로세스 중단
     2. 메모리에 없는 유효한 참조
  2. 빈 공간 즉, 자유 프레임(free frame)을 검색
  3. 새로이 할당된 프레임으로 해당 페이지를 읽어 들이도록 요청
  4. 페이지 테이블을 갱신 (유효 비트 세트)
  5. 페이지 부재 트랩에 의해 중단되었던 명령어를 다시 수행

요구 페이징의 성능(Performance of Demand Paging)

유효 접근 시간(effective access time) = (1-p) ma + p (페이지 부재 처리 시간)

• p : 페이지의 부재 확률, 0≤p≤1.0
• ma : 메모리 접근 시간(memory access time)
• 페이지 부재 처리 시간 : 인터럽트 처리, 페이지 읽기, 프로세스 재시작

쓰기 시 복사(copy-on-Write)

• 가상 메모리는 프로세스 생성(fork()) 시 페이지를 공유하여 생성 시간을 줄임
  • 쓰기 시 복사 적용
• 쓰기 시 복사(copy-on-write)
  • 자식 프로세스가 시작할 때 부모의 페이지를 당분간 함께 공유하여 사용
  • 둘 중 한 프로세스가 공유 중인 페이지에 쓸 때 페이지의 복사본이 생성
  • 수정되는 페이지만 복사본을 만들어 효율적인 프로세스 생성

💟 페이지 교체(Page Replacement)

• 모든 메모리가 사용 중이어서 빈 프레임이 없는 경우는? → 페이지 교체
• 페이지 교체 알고리즘(Page replacement algorithm)
  • 새로운 페이지는 메모리로 가져옴
  • 교체되는 페이지(victim)는 디스크에 저장
    • 수정된 페이지만을 디스크에 저장하여 페이지 전송 오버헤드 줄임
    • 변경 비트(modify bit, dirty bit) 사용
  • 성능
    • 페이지 부재가 최소가 되도록 기대
    • 일부 페이지는 자주 교체되어 메모리에 여러 번 가져오는 경우도 발생

기본적인 페이지 교체

1. 디스크에서 필요한 페이지의 위치를 알아냄
2. 빈 페이지 프레임을 찾음
   1. 빈 프레임이 있다면 그것을 사용
   2. 없다면 희생될(victim) 프레임을 선정하기 위하여 페이지 교체 알고리즘을 가동
   3. 희생될 페이지를 디스크에 기록하고, 관련 테이블을 수정
3. 새롭게 비워진 프레임에 새 페이지를 읽어오고 테이블을 수정
4. 사용자 프로세스를 재시작

페이지 교체 알고리즘(Page Replacement Algorithm)

• 페이지 부재율(page-fault rate)이 가장 낮은 것을 선정
• 페이지 교체 알고리즘의 성능
  • 특정 메모리 참조 나열에 대해 알고리즘을 적용하여 페이지 부재 발생 횟수를 계산하여 평가
  • 메모리 주소의 나열을 참조열(reference string)이라고 함

FIFO 페이지 교체 (FIFO Page Replacement)

가장 간단한 페이지 교체 알고리즘

• Belady의 모순(Belady’s anomaly) 발생
  • 프레임을 더 주었는데 오히려 페이지 부재율은 더 증가하는 현상
• 예
  • 3개의 프레임
  • 15개의 페이지 부재 발생

최적 페이지 교체

앞으로 가장 오랜 동안 사용되지 않을 페이지를 찾아 교체

• 앞으로 가장 오랜 동안 사용되지 않을 페이지를 어떻게 알 수 있는가?-

LRU 페이지 교체 (LRU Page Replacement) 알고리즘

• 최근의 과거를 가까운 미래의 근사치로 추정
  • 가장 오랜 기간 동안 사용되지 않은 페이지를 교체
  • LRU (Least Recently Used)
• 구현
  • 계수기(counter)
    • 각 페이지 항목마다 계수기 추가
    • 페이지 참조마다 계수기 증가
    • 페이지 교체 시 가장 작은 값의 계수기의 페이지를 교체
      • LRU 페이지를 찾기 위해 페이지 테이블 검색
      • 메모리 참조마다 계수기 갱신을 위해 메모리 쓰기
  • 스택(Stack)
    • 페이지 번호의 스택을 유지 : 스택은 보통 이중 연결 리스트로 구현
    • 헤이지가 참조될 때마다 페이지 번호는 스택 중간에서 제거되어 스택 top에 놓임
      • 페이지 테이블 검색 필요 없음
      • 포인터 값 변경 오버헤드

LRU 근사 페이지 교체 (LRU Approximation Page Replacement)

• LRU 교체 알고리즘은 하드웨어 오버레드가 큼
• 근사 LRU 페이지 교체
  • 페이지 항목에 1비트 함조 비트 (refrence bit) 사용
  • 참조 비트는 0으로 초기화
  • 페이지가 참조되면 참조 비트가 1로 세트
  • 참조 비트가 0인 페이지를 교체
  • 페이지가 사용된 순서는 모름

부가적 참조 비트 알고리즘 (Additional-Refernce Bit Algorithm)

• 일정한 간격마다 참조 비트들을 기록함으로써 추가적인 선후 관계 정보를 얻음
• 각 페이지에 대해 8 비트의 시프터 레지스터(shift register) 할당
• 일정한 시간 간격마다(예를 들면 매 100 밀리초) 타이머 인터럽트(timer interrupt)
  • 참조 비트는 8 비트 정보의 최상위 비트로 이동
  • 나머지 비트들은 하나씩 오른쪽으로 이동
  • 8 비트 시프트 레지스터는 가장 최근 8 구간 동안의 그 페이지의 사용 기록을 저장

🦴참고

Operating System Concepts, 10th Ed.