OS_13_Memory Allocation and Thrashing

1. Memory Allocation

1) Allocation of Frames for Multiple Processes

• 각 프로세스는 최소한의 페이지 수가 필요하다. → 3개정도?
  • Example: IBM 370은 SS MOVE 명령어 (memory-to-memory)를 처리하기 위해 6개의 page가 필요하다.
  • instruction은 6 byte며, 2개의 page에 걸쳐 있을 수 있다.
    • 16 bit이기에 명령에 2, operand 2, operator 2
  • 2 pages to handle from
    • Indirect addressing like; add @(R1), @(R2)
  • 2 pages to handle to
• 최대 page 수는 이용할 수 있는 물리 메모리 양에 따라 결정된다.
• 이 사이에는 여전히 중요한 선택이 남아있다.
  • 두 가지 주요한 할당 방식이 있다.
    • fixed allocation
    • priority allocation

a) Fixed Allocation

• Equal allocaiton - e.g., 만약 100 frames and 5 processes, 각각에게 20 page를 준다.
• Proportional allocation - process에 크기에 따라 할당을 한다.

b) Priority Allocation

• 크기보다 우선순위를 사용하여 proportional allocion scheme를 사용한다.
• 만약 프로세스 Pi가 page fault를 발생시킨다면,
  • 해당 프로세스의 frame중 하나를 교체할 대상으로 선택한다.
  • 우선순위 번호가 낮은 프로세스의 프레임을 교체할 대상으로 선택한다.

c) Global vs. Local Allocation

• Global replacement - process는 대체 frame을 모든 frame의 집합에서 선택한다; one process는 frame을 다른 곳에서 얻어온다.
• Local replacement - 각 프로세스는 오직 자신의 allocated frame 집합 중에서 선택한다.

2. Thrashing

1) Thrashing

• 만약 process가 “enough” page를 가지고 있지 않다면, page-fault 비율이 매우 높다, 이는
  • low CPU utilization
  • OS는 multiprogramming의 정도를 높여야한다고 판단한다.
  • 다른 프로세스가 시스템에 추가된다.
• Thrasing는 process가 page in and out하는 swapping작업에 바쁜 상태
  • page swapping만 반복.

2) Working-Set Model

• 델타는 working-set window, a fixed number of page references와 동의어다
  • 델타 = 10 memory references
• WSSi (working set size of Process Pi)
  • 최근 델타개의 페이지 참조에서 참조된 총 페이지의 수
  • 델타가 너무 작으면 → 전체 지역성을 포괄 할 수 없다.
  • 델타가 너무 크면 → 여러 지역성을 포괄 할 수 있다.
  • 델타가 무한하다면 → 전체 프로그램을 포괄한다.

• D = WSSi의 총합 (total demand frames) → 사용하고 있는 page (demand)
• S = 사용 가능한 frame의 개수 (supply)
  • if D > S - > Thrashing
• Policy
  • 만약 D > S, process를 중단시킨다.
    • inactive(잘 안쓰는) process를 하나 죽인다.

3) Keeping Track of the Working Set

• 대략적인 값을 이용한 근사화
  • interval timer + a reference bit + 2 in-memory bits
• Example : 델타 = 10000
  • Timer interrupt가 5000단위로 발생한다.
  • 각 페이지 마다 메모리 내에 2개의 bit를 유지한다.
  • 페이지가 참조될 때마다 reference bit를 1로 설정한다.
  • 타이머 인터럽트가 발생 시, Reference bit를 복사하고 초기화 한다.
  • memory 내 bit 중 하나가 = 1, page는 working set에 속한다.
  • Example
    • 초기에는 reference bit = 0, in-memory bits = 00
    • Read or write at time 500 → reference bit = 1
    • Interrupt at time 5,000 → in-memory bits = 10, reference bit = 0
    • Interrupt at time 10,000 → in-memory bits = 01 (shift), reference bit = 0
    • Interrupt at time 15,000 → in-memory bits = 00 (shift), reference bit = 0
    • Read or write at 17,000 → reference bit = 1
    • Interrupt at time 20,000 → in-memory bits = 10, reference bit = 0
  • 왜 이것이 정확하지 않은가?
    • 예시에서는 page가 0~4999시간 동안 working set에 포함되지 않았다.
    • 개선 가능한 방법은 10 in-memory bit를 사용하고 1000 단위 시간마다 인터럽트를 발생 시키는 것이다.
• 프로세스 마다 추적하는 것도 overhead
• 인터럽트 발생 시간을 줄일 수록 정확해지지만 overhead가 커진다.

4) Page-Fault Frequency Scheme

• PFF를 사용하여 thrashing에 대처하는 또다른 전략
• “허용 가능한” page-fault rate를 설정한다.
  • 만약 actual rate가 너무 낮으면, process는 frame을 잃는다.
  • 만약 actual rate가 너무 높으면, process는 framed을 얻는다.
• 만약 page fault rate가 높고 free frame이 없는 경우, 일부 process는 중단 될 수 있다.

3. More Concepts and Techniques

1) Optimizations

• Optimization techniques
  • Copy-on-write
  • Memory-mapped files
  • Modify bit
  • Prepaging
• Performance related topics
  • Page size
  • TLB reach
  • Belady’s Anomaly

2) Copy-on-Write

• fork()는 child를 위해 parent’s address의 복사본을 만든다.
  • parent의 page를 복제한다.
• Copy-on-Write(COW)는 부모와 자식 프로세스가 처음에는 동일한 pages를 메모리에서 공유할 수 있게 한다.
  • 두 프로세스 중 하나가 공유된 페이지를 수정하는 경우에만 page가 복사된다.
  • COW는 수정된 페이지만 복사하므로 프로세스 생성이 더 효율적으로 이루어 질 수 있다.
  • COW를 위해서 “zero-fill-on-demand”를 사용한다.
    • exec을 안해도, 메모리를 주기 전에 zero-fill을 하고 준다.
      • ex) 전역변수 → 0으로 초기화, 지역 변수 쓰레기 값

3) Memory-Mapped Files

• Memory-mapped file I/O는 disk block을 메모리의 페이지에 매핑하여 file I/O를 일반적인 routine memory access로 처리할 수 있게 한다.
  • Unix는 mmap() system call을 제공한다.
• File은 처음에는 demand paging을 이용하여 읽는다.
  • file system에서 file의 page size의 부분이 physical page로 읽힌다.
  • 파일에 대한 이후에 읽기/쓰기는 일반적인 메모리 access로 처리 된다.
• read() write() 호출로 file I/O를 처리하는 것이 아니라 메모리를 통해서 처리 함으로써 file access를 단순화 한다.
  • memory-mapped file에 쓰는건 반드시 즉시 disk에 기록되는 것은 아니다.
  • 일반적으로 file을 닫을 때, 모든 memory-mapped data는 disk에 다시 기록 된다.

4) Modify Bit

• modify(dirty) bit의 사용은 page transfer의 overhead를 줄일 수 있다.
• page의 modify bit는 page내의 어떤 word나 byte가 기록될 때마다 설정된다. (page에 write한 적이 있는지 없는지를 판단.)
• Disk에는 수정된 page만 기록 된다.

5) Prepaging

• Pure demand-paging은 process가 시작 될 때, 많은 page fault를 발생 시킨다.
• 한 번에 모든 page를 memory에 가져오기
  • process를 중단 시킬 때, 우리는 working set을 기억한다.
  • process를 재개할 때, 우리는 자동적으로 전체 working set을 다시 메모리에 가져온다.

6) Page Size

• Page size 선택
  • 일반적으로 4KB에서 4MB
  • 더 작은 page size
    • 개별 page fault handling의 I/O time이 줄어든다.
    • internal fragmentation이 더 작아진다.
    • page table의 크기가 커진다.
  • 더 큰 page size
    • 개별 page fault handling의 I/O time은 늘어나지만 총 I/O 시간은 줄어든다. (page fault가 줄어들기 때문에)
    • 더 큰 internal fragmentation
    • Smaller page table size

7) TLB Reach

• TLB Reach - TLB로 부터 메모리가 접근 가능한 크기
• TLB Reach = (TLB Size) X (Page Size)
  • 즉, 이 관점에서는 Page size가 크면 좋다.
• 이상적으로, 각 프로세스의 working set이 TLB에 저장 되어야한다.
  • 그렇지 않으면 page fault의 정도가 커진다.

8) Belady’s Anomaly

• OPT나 LRU는 둘 다 Belady’s anomaly에 영향을 받지 않는다.
• Stack algorithms는 절대 Belady’s anomaly를 겪지 않는다.
  • n개의 프레임의 수로 메모리에 있는 페이지에 집합이 (n+1)개의 프레임으로 메모리에 있을 때의 페이지 집합의 부분집합임을 보장한다.