[운영체제] Virtual Memory(2)

• 프로세스에게 몇 개의 프레임이 할당되는지 결정해야 함 -> Allocation of Frames
• HW/SW 측면에서 요구사항이 있음
  • instruction 수행 과정에서 page fault가 안 나려면 최소 6개의 페이지 필요
  • Loop 내의 page는 한꺼번에 allocate 되는 것이 유리함
  • 그렇지 않으면 매 loop page fault 발생 

Fixed Allocation

• 프로세스의 크기에 따라 고정적인 프레임 개수 할당하는 방식, 크기 비례 할당

Fixed Allocation

Priority Allocation

• 프로세스 중요도 기반 프레임 할당
• 중요도 높은 프로세스는 빨리 끝나야 됨 -> 프레임 많이 할당 -> page fault(I/O) 적게 발생 -> waiting 상태 감소

 

=> 크기나 중요도만으로 프레임을 할당했을 때 너무 많이 page fault가 생기기도, 너무 적게 생기기도 함

Local Replacement: 자신에게 할당된 프레임 내에서 victim 선정; 원래의 방식

Global Replacement: 다른 프로세스의 프레임 중에서도 victim 선정할 수 있도록

 

Thrashing

• 충분한 페이지 프레임이 없으면 page-fault 발생률이 너무 높아짐
• I/O 발생 -> CPU utilization 낮음 -> long scheduler는 CPU가 놀고 있다고 판단해서 더 많은 프로세스를 시스템에 편입 -> MultiProgramming Degree(MPD) 가 높아짐 ->  메모리를 나눠줘야 돼 -> 기존의 프로세스에서 뻇어야 되니까 메모리 더 부족해 -> page fault 더 발생해 -> CPU utilization 더 낮아 -> ... 악순환
• 이런 상황이 Trashing임

Trashing

• 과도하게 많은 프로세스가 동시에 돌아가면 안 됨
• 대응 방안은 현재 각 프로세스가 자주 접근하는 페이지들이 메모리에 올라오도록 보장해줘야 하는데 어려움
• 각 프로세스 locality 크기의 합 > 메모리 사이즈 합 => trashing 발생

 

Locality

• 프로그램이 어떤 순간에는 현재 접근하는 소수의 페이지만 계속 접근하는 것
• 임의시간 t 내에 프로그램의 일부분만을 집중적으로 참조
• Temporal Locality: 현재 참조된 메모리가 가까운 미래에도 참조될 가능성이 높음 (한 놈만 패는 스타일)
• Spatial Locality: 하나의 메모리가 참조되면 주변의 메모리가 계속 참조될 가능성이 높음

 

Working-Set Model

• Working-set: 일하는 페이지들, CPU가 접근하는 페이지들의 집합
• 현재 시점에서의 locality를 파악하기 위해 working set을 알아내는 것이 중요; 프레임 확보, victim으로 선정되지 않도록 보호
• 현재 시점 ti에서 최근 델타(delta) 분 동안 접근한 페이지들의 집합 -> WS(ti)
  • 델타가 너무 작으면 working set을 포괄하지 못하게 될 수도 있음
  • 델타가 너무 크면 working set이 지나간 페이지까지도 포함할 수 있음
• WSSi = 프로세스 Pi의 working set size(= working set에 포함된 페이지 개수)
• D = WSSi 전체 합 - 총 요구되는 프레임 개수
• D > m(= 사용 가능한 프레임 개수) 이면 Thrashing 발생; suspend 시켜서 메모리를 사용하지 않도록

• 페이지 교체 정책에도 적용 가능

구현의 어려움

• 각 페이지들이 working set에 속하는지 결정하려면 최근 델타 시간 내에 참조되었는지 알아야 함
• 페이지마다 참조된 시점, 시점과 델타 비교 -> overhead 장난 아님
• Approximate; reference bit 사용
  • 델타가 10000이면 각 페이지에 2개의 bit 할당
  • 5000번에 한 번씩 timer 인터럽트 -> 옆으로 bit copy
  • 제일 왼쪽 bit는 방금 카피되었으면 5000-10000시간 내 참조 여부를 알 수 있지만, 4999시간이 지날 때까지는 bit가 이동하지 않으므로 5000-14999시간까지의 정보를 담고 있게 됨 => 최악의 경우 50%의 오류
  • bit를 늘리고, interrupt를 자주 걸어주면 정확도는 올라가지만 overhead

working set - reference bit

• delta 를 어떻게 결정할 것인가? -> 더 큰 문제
• 그래서 실제로 많은 운영체제에서 사용되진 않음

Page-Fault Frequency(PFF) Scheme

• page fault 발생시킨 프로세스의 발생 빈도만 바뀌니까 page fault rate 의 수정 횟수가 바뀌지 않음 => overhead 매우 감소
• 구현 가능하지만 실제로 사용하지 않음
  • 어떤 놈을 뺏을지 판단하려면 locality에 포함되지 않는 놈을 알아야 됨

 

Virtual Memory를 사용했을 때 이점

1. Copy-on-Write

• 부모 프로세스를 자식 프로세스로 카피하지 않아도 됨, page table을 동일하게 만들어 공유 기법 사용 

2. Memory-Mapped Files

• 프로세스가 접근하는 파일 데이터 전체를 virtual address space에 mapping시켜서, file system을 통해서 read/write로 접근하는 것이 아니라 일반적인 메모리에서 데이터를 읽는 것처럼 함
• 가상 메모리를 사용하면 demand paging을 하기 때문에 접근하는 페이지만 메모리로 올라오니까 불필요하게 모든 페이지가 올라오지 않아도 됨
• 파일에 대한 접근은 파일 시스템을 통해서 접근해야 되는데, 하드디스크에 접근하는 것이기에 시간이 엄청 오래 걸림

 

Other Issues

Prepaging

• 프로세스의 시작 단계에서 발생하는 page fault를 줄여주기 위함
• page fault가 발생하기 전에 몇 개의 페이지를 미리 프로세스에 올려버리자
  • 올렸는데 안 쓰면 손해보는 거긴 함

Page size

• page size가 커지면
• (+) address space를 자를 때 page size로 자르니까 page 개수가 줄어서 table size 줄어듦
• (+) 한 번 page fault가 발생했을 때 디스크에서 가져오는 데이터양이 많아져서 I/O 측면에서도 좋음
• (+) Locality가 하나의 페이지 안에 쏙 들어갈 가능성도 생김
• (-) frame 사이즈도 크니까 마지막 frame에서 할당됐지만 안 쓰는 메모리 생김 -> internal fragmentation
  
  • 근데 요즘엔 메모리가 워낙 커서 internal fragmentation으로 낭비되는 공간이 심각하진 않고, I/O로 인한 비효율성 같은 게 더 문제니까 페이지 사이즈가 커지는 경향임

TLB Reach

• TLB Reach = (TLB Size) * (Page Size); TLB로 주소 변환할 수 있는 메모리 양
• locality에 포함된 페이지들은 TLB Reach로 되면 좋겠다
• Page Size를 키워서 TLB Reach를 키워볼까 -> internal fragmentation 때문에 쉽지 않음
• Multiple Page Size; 페이지 사이즈를 고정하지 않고 여러 가지로 제공해서 마지막 페이지 크기를 줄이면 internal fragmentation을 방지할 수 있음 

Program Structure

• 코딩을 잘 하면 page fault를 줄일 수 있음
• int data[128][128]; 한 페이지에 각 행이 저장 ([0][0] - [0][127], [1][0] - [1][127], …)

 

I/O interlock

• 어떤 페이지는 victim으로 선정되어서는 안 된다고 선언하고 싶은 경우
• 하드 디스크에서 파일을 읽어서 usb로 카피하고 싶은데, 하드 디스크에서 버퍼에 올린 놈이 디스크로 쫓겨나면 다시 읽어야 됨
• pin을 꼽아서 얘는 빼지 마 하고 swap out 되지 않도록 lock을 걸어두는 것

 

한양대학교 강수용 교수님 운영체제 강의 내용 정리