[OS]CH9. 가상 메모리 (Virtual memory)

 

본 글은 HPC Lab의 youtube 강의를 듣고 요약한 것입니다. 모든 이미지 출처 역시 HPC Lab의 pdf 수업자료입니다.

 

Virtual storage(Non-continuous allocation)

---

• Non-continuous allocation

  • Paging system

  • Segmentation system

  • Hybrid system

• 프로그램을 여러 개의 block으로 분할해 실행 시 필요한 block들만 메모리에 적재(나머지 block들은 swap device에 존재)

 

Address mapping

---

Continuous allocation의 address mapping

• Relative address(상대주소) : 프로그램의 시작주소를 0으로 가정한 주소
• Relocation(재배치) : 메모리 할당 후, 할당된 주소에 따라 상대주소들을 조정하는 것

Continuous allocation의 address mapping

Non-continuous allocation의 address mapping

• Virtual address(가상주소) = Logical address(논리주소) : 연속된 메모리 할당을 가정한 주소
• Real address(실제주소) = Physical address(물리주소) : 실제 메모리에 적재된 주소
• Non-continuous allocation에서의 address mapping : virtual address -> real address

가상주소와 실제주소

Non-continuous allocation의 address mapping

Virtual address의 사용 효과

• 사용자는 실제 메모리보다 큰 영역을 사용한다고 느낌
• 사용자/프로세스의 입장에서 실행 프로그램 전체가 마치 메모리에 연속적으로 적재된 것처럼 사용

 

Paging system

---

프로그램을 같은 크기의 block으로 분할(이 block을 page라 한다), 메모리도 page size로 미리 분할

• page : 프로그램의 분할된 block
• page frame : 메모리의 분할 영역(page와 같은 크기로 분할)

paging system 도식화

Paging system의 특징

• 논리적 분할이 아님(크기에 따른 분할) -> page 공유(sharing) 및 보호(protection) 과정이 복잡함
• 단순히 크기에 따라 분할 -> simple & efficient
• External fragmentation X(프로세스와 메모리 모두 동일한 크기로 분할해두니까)
• Internal fragmentation O(프로세스를 page크기만큼 나눌때 남는 부분의 크기가 page 하나의 크기보다 작을 때)

Address mapping

• Virtual address : v = (p,d)
  • p : page number
  • d : displacement(offset)
• Address mapping : PT(Page Table) 사용 - PT는 메모리의 kernel 영역에 저장(?)
• Address mapping mechanism
  • Direct mapping(직접사상)
  • Associative mapping(연관사상) - TLB(Translation Look-aside Buffer)
  • Hybrid mapping

Page table 예시

 

Paging system - Direct mapping

---

• Page falut : 참조하려는 page가 메모리에 없는 경우

Paging system - Direct mapping

Paging system의 Direct mapping 알고리즘

문제점

• 메모리 접근 횟수가 2배(PT 참고 + 메모리 참고) cf.) PT도 kernel에 있으므로 사실상 메모리 영역에 존재
  • 성능 저하

해결방안

• Associative mapping(TLB)
• Hierarchical paging(나중에 별도로 정리)
• Hashed page table(나중에 별도로 정리)
• Inverted page table(나중에 별도로 정리)

 

Paging system - Associative mapping

---

• TLB(Translation Look-aside Buffer)에 PT 적재
• PT를 병렬탐색
• low overhead, high speed
• But expensive HW - 큰 PT를 적재하긴 어려움

Paging system - Associative mapping

 

Paging system - Hybrid mapping

---

• PT 중 일부 entry들만 TLB에 적재(최근에 사용된 page들에 대한 entry 저장) - PT를 위한 일종의 전용 캐시
• Locality 활용
  • cf.) temporal locality : 한 번 접근한 영역을 다시 접근할 가능성이 높은 것, spatial locality : 접근한 영역의 인접한 곳을 다시 접근할 가능성이 높은 것

Paging system - Associative mapping 알고리즘

Paging system - Associative mapping

 

Paging system의 memory management

---

• Page와 같은 크기로 미리 분할하여 관리/사용 - Page Frame
• Frame table : page frame의 정보를 담은 table
  • allocated/available field
  • PID filed
  • Link field : 사용가능한 곳 연결(for free list)
  • AV : free list의 시작점(Free list header)

Frame table 예시

 

Page sharing

---

여러 프로세스가 특정 page를 공유 가능(Non-continuous allocation!!)

• Procedure page sharing
• Data page sharing

Page sharing 예시

Page sharing에선 아래 그림처럼 서로 같은 곳을 가리키지만 PT의 page frame number가 다른 경우가 발생한다.

Page sharing problem

이를 해결하기 위해선, 아래 그림처럼 shared page에 대한 정보를 프로세스들이 PT의 같은 entry에 저장하도록 하면 된다.

Solution to page sharing problem

 

Page protection

---

여러 프로세스가 page sharing할 때, page의 접근 권한을 설정하는 것(protection bit 사용)

page protection

 

Paging system 요약

---

프로그램을 고정된 크기의 block(page)로 분할, 메모리도 page size로 미리 분할

장점

• 외부 단편화 해결
• 필요한 page만 page frame에 적재(메모리의 효율적 활용)

단점

• 내부 단편화
• 프로그램의 논리적 구조 고려하지 않아 page sharing/protection이 복잡
• page mapping overhead(PT를 위한 메모리 공간 및 추가 메모리 접근이 필요)

 

Segmentation system

---

프로그램을 논리적 block(segment)으로 분할 - block 크기가 서로 다를 수 있음

특징

• segment sharing/protection이 용이
• mapping overhead
• Internal fragmentation X
• External fragmentation O

Segmentation system

Segmentation system

Address mapping

• Virtual address : v = (s,d)
  • s : segment number
  • d : displacement(offset)
• ST(Segment Table) 사용
• Address mapping mechanism : paging system과 유사

Segment table 예시

Segment system - direct mapping 예시

Segment system - direct mapping 알고리즘

 

Segment system의 memory management

---

segment 적재 시, 크기에 맞추어 분할 후 적재

segment system의 memory state table

 

Segment sharing/protection

---

논리적으로 분할되어 있어, 공유 및 보호가 용이함

Segment sharing

 

Segment system 요약

---

프로그램을 논리 단위로 분할(segment), 메모리를 동적으로 분할

장점

• 내부 단편화 해결
• 논리단위로 분할 -> segment sharing/protection이 용이함
• 필요한 segment만 메모리에 적재(메모리 효율적 사용)

단점

• paging system 대비 overhead 큼
• segment mapping overhead(ST를 위한 메모리 공간 및 추가적 메모리 접근 필요)

paging system vs. segmentation system

 

Hybrid system

---

논리 단위의 segment로 프로그램을 분할해 각 segment를 고정된 크기의 page들로 분할 후 메모리에 page 단위로 적재

Hybrid system

Address mapping

• Virtual address : v = (s,p,d)
  • s : segment number
  • p : page number
  • d : displacement(offset)
• ST, PT 모두 사용
  • 각 프로세스마다 하나의 ST
  • 각 segment마다 하나의 PT
• Address mapping mechanism : direct, associated 등

Hybrid system의 ST 예시

Hybrid system의 PT 예시

Hybrid system의 address mapping

Hybrid system - direct mapping 예시

 

Hybrid system 요약

---

논리적 분할(segment)와 고정크기 분할(page)을 결합

장점

• page sharing/protection이 쉬움
• 메모리 할당/관리 overhead 작음
• 외부 단편화 해결

단점

• 내부 단편화 발생 가능
• 전체 table 수 증가(메모리 소모 큼, address mapping 과정 복잡)
• Direct mapping의 경우, 메모리 접근이 3배(성능 저하)