[OS] KOCW 운영체제 강의 정리 (14) | Chapter 8. Memory Management - 2

 

Chapter 8. Memory Management - (2)

 

---

 

💡 Contiguous Allocation

1. Fixed partition allocation (고정 분할 방식)

• 물리적인 메모리를 몇 개의 영구적 분할 (partition)으로 나눔
• 분할의 크기가 모두 동일한 방식과 서로 다른 방식이 존재
• 분할 당 하나의 프로그램 적재
• 융통성이 없음
  • 동시에 메모리에 Load되는 프로그램의 수가 고정됨.
  • 최대 수행 가능 프로그램 크기 제한
• 외부 조각 (External Fragmentation)
  • 분할된 부분이 작아서 생기는 문제
• 내부 조각 (Internal Fragmentation)
  • 분할된 부분이 커서 남는 부분이 발생해서 생기는 문제

2. variable partition allocation (가변 분할 방식)

• 프로그램의 크기를 고려해 할당하는 방식
• 분할의 크기, 개수가 동적으로 변형
• 기술적 관리 기법 필요
• 외부 조각 (External Fragmentation) 이 발생할 수 있음.

3. Hole

• 가용 메모리 공간
• 다양한 크기의 hole들이 메모리 여러 곳에 흩어져 있음.
• 프로세스가 도착하면 수용 가능한 hole을 할당
• 운영체제는 할당 공간(사용중인 공간), 가용 공간(hole) 정보를 유지함.

4. Dynamic Storage Allocation Problem

• 가변 분할 방식에서 size n인 요청을 만족하는 가장 적절한 hole을 찾는 문제

1. First-fit
   • size가 n 이상인 것 중 최초로 찾아지는 hole에 할당
2. Best-fit
   • Size가 n 이상인 가장 작은 hole을 찾아서 할당 (프로그램의 크기와 가장 비슷한 Hole 탐색)
   • Hole들의 리스트가 크기순으로 정렬되지 않은 경우 모든 hole의 리스트를 탐색해야 함.
   • 많은 수의 아주 작은 hole들이 생성됨. 3, Worst-fit
   • 가장 큰 hole에 할당.
   • 역시 모든 리스트를 탐색해야 함.
   • 상대적으로 아주 큰 hole들이 생성됨.

• First-fit과 Best-fit이 Worst-fit보다 속도와 공간 이용률 측면에서 더 효과적인 것으로 알려짐. (실험적인 결과, 약간 당연하기도 함)

5. Compaction

• External Fragmentation(외부 조각) 문제를 해결하는 한 가지 방법
• 사용 중인 메모리 영역을 한군데로 몰고 hole들을 다른 한 곳으로 몰아 큰 block을 만드는 것
• 매우 비용이 많이 드는 방법임
• 최소한의 메모리 이동으로 compaction하는 방법 (매우 복잡한 문제)
• Compaction은 프로세스의 주소가 실행 시간에 동적으로 재배치 가능한 경우에만 수행될 수 있다.

 

💡 Noncontiguous Allocation

• 주소 변환을 페이징 별로 해야하기 때문에 바인딩이 어려워짐.

1. Paging (페이징 기법)

• Process의 Virtual Memory를 동일한 사이즈의 Page 단위로 나눔
• Virtual Memory의 내용이 page 단위로 noncontiguous하게 저장됨.
• 일부는 backing storage에, 일부는 physical memory에 저장됨.
• Basic Method
  • Physical memory를 동일한 크기의 frame으로 나눔.
  • Logical memory를 동일 크기의 page로 나눔 (frame과 같은 크기)
  • 모든 가용 frame들을 관리
  • page table(각각의 페이지의 주소공간을 관리하는 배열)을 사용하여 logical address를 physical address로 변환
  • External fragmentation 발생 안함 (같은 크기로 분할하기 때문)
  • Internal Fragmentation 발생 가능
    (마지막에 페이지 하나보다 남는 공간이 생길 수 있음. memory 공간이 페이지 개수만큼 할당되지는 않기 때문에.)

• 주소변환을 위해 paging table(배열)이 사용됨.
• page가 들어갈 수 있는 공간을 paging frame이라고 함.

• 앞부분이 논리적인 페이지 번호(p) / 뒤부분은 논리적인 주소(d)

Implementation of Page Table

• Page table은 main memory에 상주
• Page-table base register(PTBR)가 page table을 가리킴
• Page-table length register(PTLR)가 테이블 크기를 보관
• 모든 메모리 접근 연산에는 2번의 memory access 필요
• page table 접근 1번, 실제 data/instruction 접근 1번
• 속도 향상을 위해 associative register or translation look-aside buffer(TLB)라 불리는 고속의 lookup hardware cache 사용 (별도의 하드웨어를 사용하여 속도 향상을 도모함)

• 메모리 주소 변환을 위해 별도의 cache memory를 두는 것을 TLB라고 보면 됨.
• 페이지 테이블에 대한 일부 데이터를 caching함.
• TLB를 주소 변환 전에 먼저 검색하여 데이터를 체크하고, 존재한다면 바로 주소변환이 발생함.
• 정보 전체를 담고 있는 것이 아니라 빈번이 참고되는 일부 데이터만을 담고 있기 때문에 물리적/논리적 페이지의 쌍을 가지고 있음.
• TLB는 전체를 search해야 하기 때문에 Associative registers를 추가로 사용하여 병행 검색(parallel search)이 가능하도록 구현함.
• Address Translation (주소 변환)
  • page table 중 일부가 associative register에 보관되어 있음.
  • 만약 해당 page #(number)가 associative register에 있는 경우 곧바로 frame #를 얻음.
  • 그렇지 않은 경우 main memory에 있는 page table로부터 frame #를 얻음
  • TLB는 context switch 때 flush (remove old entries)

Effective Access Time

• TLB로부터 주소변환이 되는 비율이 굉장히 높기 때문에 입실론(e)의 비율은 굉장이 적다.

 

Two-Level Page Table

• Outer-page table / Inner-page table(page of page table) 이렇게 두가지 테이블 사용
• 속도는 줄어들지 않지만, 메모리 사용량이 줄어들기 때문에 사용함.
• 현대의 컴퓨터는 address space가 매우 큰 프로그램을 지원함.
  • 32bit address 사용 시 : 2의 32승 Byte (4GB)의 주소 공간
    • page size가 4K일 시 1M개의 Page table entry 필요.
    • 각 page entry가 4Byte일 시 프로세스 당 4M의 page table 필요.
    • 그러나, 대부분의 프로그램은 4G의 주소 공간 중 지극히 일부분만을 사용하므로 page table 공간이 심하게 낭비됨.
  • page table 자체를 page로 구성하면 사용되지 않는 주소 공간에 대한 outer page table의 엔트리 값은 null (대응하는 inner page table이 없음, 그러므로 메모리 공간을 아낄 수 있음.)
• 페이지 테이블도 영역을 나누어 관리하는 것
• Logical address (on 32-bit machine with 4K page size)의 구성
  • 20 bit의 page number
  • 12 bit의 page offset
• page table 자체가 page로 구성되기 때문에 page number는 다음과 같이 나뉘게 된다.
  • 10-bit page number
  • 10-bit page offset
• 따라서, logical address는 page number (p1 - 10bit, p2 - 10bit)와 page offset (d - 12bit)로 구성되어 있게 된다.

• 여기서 p1은 outer page table의 index이고, p2는 outer page table의 page에서의 변위 (displacement)가 된다.

 

---

⬇︎⬇︎ 강의 링크 ⬇︎⬇︎

http://www.kocw.net/home/search/kemView.do?kemId=1046323 

운영체제