[운영체제] 9. Virtual Memory

Virtual address

• virtual address space : 프로세스 내의 주소 표현을 논리적으로 나타냄
  • 0으로 시작하여 연속적으로 표현
• demand paging
  

  

  • 프로세스의 필요한 페이지만 필요할 때 할당하는 것
  • I/O가 덜 필요하거나 아예 쓸 필요가 없음
• page fault
  • logical memory에서 page table 접근 시 invalid한 경우
  • 다른 page table을 참조하게 되는 경우

---

• demand paging 단계
  • 레지스터와 프로세스 상태 저장
  • page fault로 인한 인터럽트 여부 확인
  • page table의 valid 여부, page 위치 확인
  • 저장소에서 frame으로 read 요청
    • 요청을 큐에 할당
    • 장치의 seek/latency time동안 대기
    • page를 free frame으로 전송
  • 대기 중일 때는 CPU는 다른 사용자에게 할당
• demand paging 시의 EAT
  • 주된 동작 : 인터럽트 서비스, page read, process restart
  • page fault rate p를 가정 (p=0 : no page fault)
  • EAT = (1 - p) * 메모리 접근 + p * (page fault overhead + swap In + swap Out)

Copy on Write

• 프로세스 fork 시 부모 - 자식 프로세스가 같은 page를 공유하게 하는 것
  • 자식 프로세스 생성 시에는 프로세스 공간을 복사하지 않음
  • 한 쪽의 프로세스가 write 동작 시 page 복사가 일어남
• page replace
  • page의 과한 할당을 방지
  • page overhead를 줄이기 위한 modify(dirty) bit 사용 - 수정된 page만 write

Page replace

• 제한된 메모리 상의 process 할당 시 page 전환이 필요
• 여유 공간이 없을 경우 page를 전환하여야 함
• page replace 단계
  • page 할당이 필요할 때, free frame을 탐색
  • free frame이 없을 경우, 제거될 frame(victim frame)을 선택
  • victim frame은 저장소로 swap out / 필요 데이터는 그 자리로 swap in
• replace algorithm
  • frame - allocation : 프로세스당 프레임을 얼마나 할당할지, 어떤 프레임을 재할당할지
  • page - replacement : page fault rate를 최소한으로 하도록
  • reference string : 접근한 page 기록을 저장하여 replace 알고리즘에 사용
• FIFO
  

  

  • 가장 먼저 들어온 page를 replace
  • page fault는 10번 발생 (처음부터 계속 page가 없어 replace함)
  • belady's anomaly : frame 수가 늘어나면 오히려 page fault가 많아질 수 있음
• Optimal algorithm
  

  

  • 가장 오래 사용될 페이지는 유지
• Least Recently Used(LRU)
  

  

  • 가장 사용되지 않은 데이터를 교체
  • 미래를 예측하는 Optimal과 달리 과거 데이터를 활용
• second chance algorithm
  

  

  • FIFO와 유사
  • reference bit가 0이면 교체
  • reference bit가 1이면 0으로 변경
  • enhanced second chance
    • (reference, modify)로 2개 bit 할당
    • (0, 0) : replace
    • (0, 1) : replace 전에 메모리 write
    • (1, 0), (1, 1) : 다음 접근 시 replace
    • ex. (1, 1) > (0, 1) > (0, 0) - 3번의 반복을 통해 victim frame이 됨

Buddy System

• $2^n$ allocater를 이용한 메모리 할당
• Slab : 1개 이상의 연속된 page
  • 캐시는 하나 이상의 Slab로 구성
• prepaging
  • page fault 방지를 위해 미리 page 할당
• program 구조
  • 2차원 array int[a, b]를 가정
  • 각 row에는 page가 저장됨
  • 위 코드는 col마다 접근하기 때문에 a * b번의 page fault가 발생하나, 아래 코드는 page fault가 row 개수만큼만 발생

for(j=0;j<a;j++)
    for(i=;i<b;i++)
        data[i, j]=0


for(i=;i<b;i++)
    for(j=0;j<a;j++)
        data[i, j]=0

• I/O Interlock
  • 프로세스가 I/O 장치를 접근할 때, 해당 프로세스가 swap되는 경우
  • 프로세스는 물리적 주소가 할당되기 전이지만, 데이터는 여전히 입력되어야 하는 상태가 됨
  • 이로 인한 문제를 방지하기 위해 프로세스의 해당 page를 swap되지 못하도록 함 (Pinning)