가상메모리(1)

<배경>
- "현재 실행되고 있는 코드들은 반드시 물리적 메모리에 존재해야 한다"
  - 앞서 다룬 메모리 관리 기법들의 특징
  
  - 방법
    - 프로세스 전체를 메모리에 적재
      - 가장 손쉬운 방법
    - Dynamic Loading
      - 프로그래머의 특별한 주의와 추가 작업 필요

  - 단점
    - 프로세스의 크기가 물리적 메모리의 크기로 제한





<주소 공간과 물리 메모리>
- 컴퓨터에 설치 가능한 물리 메모리의 한계
  - CPU의 주소 버스 크기에 좌우
  - 32비트 CPU의 물리 메모리 최대량 : 2^32B = 4GB
  - 64비트 CPU의 물리 메모리 최대량 : 2^64B = 2^24TB

- 실제 설치되는 물리 메모리
  - 현재 대부분 8~32GB정도 장착
    - 비용적인 한계






<물리 메모리의 한계>
- 물리 메모리보다 큰 크기의 프로세스는 실행될 수 없다!
- 동시 수행되는 프로세스들의 크기의 총합은 물리 메모리보다 클 수 없다!







<메모리에 모든 내용이 있어야 하는가?>
- 프로그램의 모든 부분이 동시에 요구되진 않음
  - 순차적 실행

- 항상 모든 코드가 메모리에 적재되어 있어야 하지는 않음
  - 오류 상황을 위한 코드
  - 잘 사용하지 않는 기능에 대한 코드
  - 필요 이상으로 할당된 큰 용량의 배열






<그러면 가능한 대안은?>
- 물리 메모리를 보조저장장치로 확장
  - 프로세스를 메모리와 보조장치에 나누어 저장
  - 프로세스를 실행하기에 충분히 큰 메모리가 있다고 착각하게 만드는 메모리 관리 기법

- 스와핑(Swapping)
  - 메모리가 부족할 때, 실행에 필요하지 않는 부분은 보조저장장치로 이동
  - 실행에 필요할 때 보조저장장치로부터 물리 메모리로 이동






<가상 메모리(Virtual Memory)>
- 물리메모리 영역을 보조저장장치까지 연장
  - 스왑(swap)
  - 무한의 가상적인 메모리 공간

- 실행을 위해 프로세스의 일부만을 메모리에 할당
- 가용 메모리 부족 시 일부 내용을 스왑 영역으로 옮겨 빈 영역 확보
  - 다중 프로그래밍 정도를 높여 CPU 이용률/처리율 향상
  - 스왑-아웃, 스왑-인

- OS 마다 세부 구현 방법은 다름
  - 요구 페이징, 요구 세그멘테이션 등

<일부만 메모리에 적재할 수 있다면?>
- 프로세스의 크기가 물리적 메모리의 크기에 의해 제약 받지 않을 수 있다
  - 프로그래밍 작업이 간단해짐

- 다중 프로그래밍 정도가 늘어남
  - Turnaround time과 response time이 늘어나지 않으면서 CPU utilization과 throughput 향상

- 보다 빠른 실행이 가능
  - 적재 속도의 향상
  - swap을 위한 입출력이 줄어듦






<Process 실행 관련 주요 용어>
- CPU utilization(이용률)
  - CPU가 얼마나 많이 이용되는가

- Throughput(처리량)
  - 단위 시간 동안 수행이 완료된 프로세스 개수

- Turnaround time(총 처리 시간)
  - 임의의 프로세스를 수행하는데 걸리는 시간

- Response time(응답 시간)
  - 요청을 보낸 후 첫 응답이 발생하기 까지 걸린 시간






<Virtual Memory 사용의 기본적인 이점>
- 프로세스간의 메모리 공유를 가능하게 한다
  - 각 프로세스는 각자 자신의 주소 공간을 사용하는 것처럼 보인다
  - 여러 프로세스 간에 시스템 라이브러리를 공유

- 프로그램 실행 중에 사용되는 메모리의 양/배치 방법 등에 대해 신경쓰지 않아도 된다
  - 무한의 메모리라 가정 가능

- 메모리 계층 구조에서 높은 access rate와 비트 당 낮은 저장 비용(low cost per bit)위해






<가상 메모리 시스템의 주요 동작>
- 프로세스의 처리 요구에 따라 서로 다른 레벨의 메모리 간의 정보 블록들의 스와핑

- 주요 결정 사항
  - 인출 정책(Fetch policy) : 언제 가져올 것인가?
  - 배치 정책(Placement policy) : 어디로 가져올 것인가?
  - 교체 정책(Replacement policy) : 어느 frame과 교체할 것인가?






<가상 메모리 관련 문제들>
- 가상 메모리의 페이지 테이블 구성
- 페이지 폴트
- 페이지 할당
- 스왑 영역
- 프레임 할당
- 스레싱
- 작업 집합
- 페이지 교체 알고리즘
- 쓰기 시 복사







<요구 페이징(Demand Paging)>
- 필요한 page들만 물리 메모리에 적재하는 방법
  - 실행중에 page들이 실제 필요할 때에 적재된다
  - 사용되지 않는 page는 적재되지 않음
  - 페이지를 갖는 보조기억장치 영역 : 실행파일 + 스왑

- 장점
  - Less I/O needed
  - Less memory needed
  - Faster response
  - More users
 
 
 
<요구 페이징의 구성>

<스왑(swap) 영역>
- 메모리가 부족할 때, 메모리를 비우고 페이지를 저장해두는 하드 디스크 영역
  - 리눅스 : swap 파티션
  - MS-Windows : C\pagefile.sys 파일

- 스왑-인(swap-in)
  - page-in 이라고도 부르며, 스왑 영역에서 한 page를 메모리 frame으로 읽어들이는 행위

- 스왑-아웃(swap-out)
  - page-out 이라고도 부르며, 메모리 frame에 저장된 page를 스왑 영역에 저장하는 행위






<가상 메모리에서의 페이지 테이블>
- valid/presence bit
  - 해당 page가 물리 메모리에 있는지 여부
    - 1 : 해당 page가 frame 번호의 메모리에 있음
    - 0 : 해당 page가 디스크에 있음

- modified bit(dirty bit)
  - 해당 page가 수정되었는지 여부
    - 1 : 해당 page가 수정되었는지 여부
      - 스왑 아웃될 때 스왑 영역에서 저장 필요

     - 0 : 해당 page는 수정된 적이 없음
      - 스왑 아웃될 때 스왑 영역에 저장 불필요






<페이지 부재(Page Fault)>
- 메모리에 없는 page가 참조할 때 페이징 하드웨어가 OS에게 보내는 trap

- Page fault에 대한 처리 과정
  1. 프로세스에 대한 page table을 통해 해당 참조가 유효한지 검사
    - Invalid reference => abort
    - Just not in memory => 디스크에서 가져와야 함
  2. Free frame을 찾아 디스크로부터 page를 가져옴
  3. Page table 갱신
  4. Page fault에 의해 중단된 intrsuction 재실행
 
 
 
<페이지 부재 처리 과정>

<중단된 Instruction의 재실행>
- Demand paging을 위한 필수적 요구사항

  - 일반적으로 중단된 프로세스의 상태를 나타내는 각종 레지스터들의 값을 저장해두었다가 복원

  - Instruction fetch시 발생된 경우
    - 해당 page를 메모리로 가져온 후 다시 시도

  - Operand fetch/execution시 발생된 경우
    - 해당 page를 메모리로 가져온 후, 해당 instruction을 다시 인출하여 실행
    - 반복 작업이 수반되나 감수할 만함






<가상 메모리에서 새 프로세스 생성>
- fork() 시스템 호출로 생성되는 프로세스
  - 메모리 할당 + 페이지 적재

- fork() 시스템 호출
  - 방법 1 : 완전 복사
  - 방법 2 : 쓰기 시 복사






<방법 1 : 완전 복사>
- 부모 프로세스의 모든 페이지를 온전히 복사
- 많은 경우 fork() 후 바로 exec() 하기에 비효율적
  - ex)
int childPid == fork(); //쉘을 복제한 자식 프로세스 생성
if(childPid == 0){ //자식 프로세스 코드
execlp("/bin/ls", "ls", NULL); // /bin/ls 파일을 적재하여 실행
} // execlp()에 의해 자식 프로세스의 메모리가 모두 반환되고 실행 파일 ls로부터 새로 페이지 적재

<방법 2 : 쓰기 시 복사(Copy-on-Write, COW)>
- 자식 프로세스를 위해 부모의 page table만을 복사
  - 초기에 자식은 부모의 메모리 frame을 온전히 공유

- 자식의 page table 항목에 COW(쓰기시 복사)표시를 해둠

- 부모/자식 중 하나에서 page 수정이 발생하면 새 frame 할당하고 부모 frame복사






<COW의 특징>
- 효율적인 프로세스 생성이 가능
  - 프로세스 생성 시간 절약
    - 전체 page들을 복사하지 않고 단지 변경되거나, 변경 가능한 page들만 복사
    - fork() 후 exec() 발생 시 불필요한 복사 시간의 낭비가 생기지 않음

  - 메모리 절약
    - 수정이 발생되지 않는 page는 새 frame을 할당할 필요 없음 
      - 예 : 코드 영역






<요구 페이징 관련 이슈>
- 페이지 부재가 빈번히 발생시 빈번한 입출력으로 시스템 성능이 떨어지지 않을까?
  - 그럴 수 있다 : 스레싱(thrashing)

- 실행 시 페이지 부재가 계속되면 해당 프로세스의 많은 page가 적재되는데, 애초부터 적재하지 않나?
  - 실행 과정에서 참조될 수 있는 page를 미리 알 수 없기에 

- 한 프로세스에게 할당 가능한 frame은 무한한가?
  - 물리 메모리 양의 크기로 제한됨

- 한 프로세스에게 할당하는 frame 수와 페이지 부재의 관계
  - 일반적으로 반비례 관계

- 커널 코드와 커널 데이터가 적재된 frame도 스왑-아웃되나?
  - 실행 효율성 때문에 이 둘은 항상 물리 메모리에 적재







<스레싱(Thrashing)>
- 프로세스가 실제 실행보다 더 많은 시간을 페이징 처리에 할당하고 있는 상태
  - 과도한 page 교체로 인한 swap in/out에 몰두

- 원인
  - 프로세스가 실행에 필요한 충분한 frame을 할당받지 못하면
    - page fault가 매우 낮아짐
    -> CPU 이용률이 낮아짐
    -> OS는 다중 프로그래밍 정도를 증가시키려 함
  - 악순환 반복으로 심각한 성능 저하 초래







<스레싱 현상>
- 다중 프로그래밍 정도가 높아질수록 CPU 이용률 증가
- 다중 프로그래밍 정도가 임계점(M)을 넘어가면 스레싱 발생

<스레싱 해결 및 예방>
- 감지 방법
  - OS마다 다름
    - MS 윈도 : process explore 등 사용
    - 리눅스 : top, htop, vmstat 명령
  - 작업 부하는 높지만 CPU 이용률이 낮고, 스왑-인/아웃이 모두 높은지 검사

- 해결 및 예방
  - 다중 프로그래밍 정도 줄이기
    - 일부 프로세스 종료
  - 빠른 보조저장장치의 사용
  - 물리 메모리 증가







<참조의 지역성(reference of locality)>
- CPU가 짧은 시간 범위 내에 일정 구간의 메모리 영역을 반복적으로 참조하는 경향
  - locality(지역성), principle of locality(지역성의 원리)
    - 프로그램이 가진 기본적인 실행 특성
 
  - 짧은 시간 동안에는 메모리에 균일하게 접근하기보다는 특정 부분에 집중 참조하는 경향을 지님
    - 프로세스는 최근에 참조한 데이터와 코드를 다시 참조하는 경향성
    - 참조의 지역성 이동. 프로세스가 실행되는 동안 메모리 영역을 옮겨 다니면서 참조의  지역성이 나타남
 
  - 경험적 관찰에서 발견된 90/10 규칙
    - "프로그램 코드의 10%에서 실행 시간의 90% 소비"








<참조의 지역성의 형태>
- 시간 지역성(temporal locality)
  - 시간적으로 볼 때, 
    - 프로세스에서 현재 참조된 주소(페이지)가 가까운 미레에 다시 참조될 가능성이 큰 특성
    - 코드나 데이터, 자원 등이 짧은 시간 내에 다시 사용되는 특성 : 반복문

- 공간 지역성(spatial locality)
    - 공간적(메모리 주소)으로 볼 때,
      - 현재 참조되는 번지(페이지) 주변의 번지들이 가까운 미래에 참조될 가능성이 큰 특성
      - 순차적 실행, 배열, 순차 읽기/쓰기






<참조의 지역성의 의미>
- 현재 프로세스의 실행 패턴을 관찰하면
  - 가까운 미래에 어떤 페이지에 접근할 것인지 합리적으로 예측 가능
 
- 메모리 할당과 페이지 교체 전략에 활용







<작업 집합(working set)>
- 일정 시간 범위 내에 프로세스가 참조한 페이지들의 집합
  - 현재 프로세스의 실행에 필요한 페이지들의 집합
    - 작업 집합에 포함된 페이지들이 모두 메모리에 적재되어 있는 것이 프로세스 실행 최고 성능
  
  - 참조의 지역성으로 작업 집합은 뚜렷이 형성됨
    - OS는 프로세스에게 작업 집합을 적재할 수 있는 정도의 메모리 할당할 필요가 있음
      - 부족 시 잦은 스와핑 발생







<작업 집합과 시간 범위>
- 페이지 부재는 작업 집합을 메모리에 적재하는 과정
  - 참조의 지역성으로 인해 일정 시간 내에 작업 집합 형성
  - 시간 범위가 클수록 작업 집합도 큼
    - 시간 범위를 얼마로 정할 것인가?







<작업 집합 이동(working set shift)>
- 스레싱이 아닌 경우 page fault rate는 시간에 따라 고점과 저점 사이를 오르내림
  - 고점 : 새로운 지역으로 진입

<스레싱과 작업 집합>
- 스레싱 발발 원인 설명에 작업 집합 모델 활용
  - 1968년 Denning의 논문(Thrashing : its causes and prevention)
    - 스레싱의 원인 설명에 '작업 집합' 모델 사용
      - 처음 스레싱 관측
      - 1968년 처음으로 작업 집합 모델로 스레싱 현상을 설명

- 스레싱 예방
  - 스레싱은 작업 집합이 메모리에 올라와 있지 않을 때 발생
  - 1968년 Denning, 실험으로 증명
    - 예방책 제시 - 각 프로세스에게 작업 집합에 포함하는 페이지들을 적재할 충분한 메모리 할당