/ OS

OS(11) - Contiguous Memory Allocation

OS 관련 포스팅

Contiguous Memory Allocation (연속 메모리 할당)

  • 최초의 컴퓨터
    → OS 없음
    → 하나의 process만 main memory에서 돎
  • OS 등장
    → OS와 하나의 process가 돎
    → MS-DOS
  • Multi-programming 환경
    → OS와 여러 개의 process가 돎
    → booting 직후에는 OS와 big single hole(비어있는 하나의 큰 메모리)
    → process 생성과 종료의 반복 후에는 OS와 scattered holes(흩어져있는 여러 메모리)
    → memory가 흩어져 있으면 새 process 적재 불가
    (hole을 모두 합하면 적재할 process 용량보다 커도 이어져있지 않으면 사용 불가) (= 외부 단편화(external fragmentation))
  • 연속 메모리 할당 방식
    • First-fit
      → memory를 위(또는 아래)에서 순차적으로 훑어 처음으로 만난 적합한 공간에 할당
    • Best-fit
      → 빈 hole 중에서 새 process 용량과 가장 크기가 비슷한 곳에 할당
    • Worst-fit
      → 빈 hole 중에서 새 process 용량과 가장 크기가 크게 차이나는 곳에 할당
    • 속도: first-fit이 가장 빠름
      → 조건에 부합하는 첫 메모리 공간에 할당하기 때문
    • 이용률: first-fit, best-fit 방식이 실행 못하는 process 수가 비교적 적음
    • first-fit이나 best-fit을 선택하더라도
      여전히 external fragmentation 발생
      → memory의 약 1/3은 사용 불가
    • compaction: 흩어져 있는 hole들을 한 곳으로 모으는 것
      → 최적의 알고리즘의 부재, 고부담의 단점이 존재

Paging (페이징)

  • memory에 process가 연속 할당되어야 한다는 생각때문에 발생한 external fragmentation의 해결책
  • memory를 일정한 크기(= frame)로 자르고 process 역시 같은 일정한 크기(= page)로 자름
    → size: frame = page
  • 여러 개의 MMU가 relocation register값을 바꿔주면 각 page들이 hole의 frame에 각각 배치될 때, CPU는 process가 연속 할당되었다고 속음
  • 이때의 MMU는 page table이라고 함

Address Translation (주소 변환) ★★★★★

  • Logical address(논리 주소)와 Physical address(물리 주소)는 MMU를 기준으로 나뉨
  • Logical address
    → CPU가 내는 주소, 2진수(binary)
    → 전체 m비트, 하위 n비트(offset 또는 displacement(d)), 상위 m-n비트(page number(p))
  • Address translation: Logical address → Physical address
    → page number: page table의 index 값
    → frame number: 해당 page number의 내용
    → displacement(변위): 변하지 않음 → page table의 entry 수 = 해당 process가 사용하는 page 수
  • 예제 # 01
    • page size = 4byte
    • page table: 5 6 1 2
    • logical address = 13
    • pysical address = ?
      sol.)
index number page table
0 5
1 6
2 1
3 2

page size (= frame size) = 4byte = 2^n = 2^2 → n = 2
logical address: 13(10) = 1101(2)
logical address = ‘page number(p)’ + ‘displacement(d)’
logical address의 뒤에서부터 두 자리(=n)는 (d), 남은 앞의 두 자리는 (p)
→ p: 11/01 :d
page number: 11(2) = 3(10)이며, page table 3번 index의 frame number는 2(10) = 10(2)
pysical address = ‘frame number(f)’ + ‘displacement(d, ※불변)’이므로
pysical address = 1001(2) = 9(10)

  • 예제 # 02
    • page size = 1KB
    • page table: 1 2 5 4 8 3 0 6
    • logical address = 3000, pysical address = ?
    • pysical address = 0x1A53, logical address = ?
      sol.)
index number page table
0 1
1 2
2 5
3 4
4 8
5 3
6 0
7 6

page size (= frame size) = 1KB = 2^n = 2^10 → n = 10
logical address: 3000(10) = 1011 1011 1000(2)
logical address = ‘page number(p)’ + ‘displacement(d)’
logical address의 뒤에서부터 열 자리(=n)는 (d), 남은 앞의 두 자리는 (p)
→ p: 10/11 1011 1000 :d
page number: 10(2) = 2(10)이며, page table 2번 index의 frame number(f)는 5(10) = 101(2)
pysical address = frame number(f):101(2) + displacement(d, ※불변): 11 1011 1000(2)이므로
pysical address = 1 0111 1011 1000(2) = 6072(10)

pysical address: 0x1A53 = 1 1010 0101 0011(2)
n = 10, pysical address = ‘frame number(f)’ + ‘displacement(d, ※불변)’이므로
→ f: 1 10/10 0101 0011 :d
frame number: 110(2) = 6(10)이며, frame number 6의 index number는 7(10) = 111(2)
logical address = page number(p):111(2) + displacement(d, ※불변):10 0101 0011(2)이므로
logical address = 1 1110 0101 0011(2) = 0x1E53

Internal Fragmentation(내부 단편화)

  • process size가 page size의 배수가 아니어서 마지막 page는 한 frame을 다 못 채우는 것
    e.g.) process: 15byte, page size: 4byte 일 때,
    | 4 | 4 | 4 | 3 |으로 마지막 frame의 남은 1byte는 못 쓰게 됨 → 낭비
  • 내부 단편화는 비교적 미미한 낭비라 큰 문제는 아님
  • 내부 단편화의 최대 크기 = page size - 1byte

page table 만들기

  1. CPU register로 page table 만들기
    • CPU 안의 기억장치인 CPU register로 page table을 만들면,
      → 장점: 주소 변환 속도 빠름
      → 단점: CPU는 memory가 아니라서 table entry 저장 용량이 작음
  2. Memory로 page table 만들기
    • main memory 안에 넣는 방법으로,
      → 장점: table entry 수가 많아도 저장 용량에 문제 없음
      → 단점: CPU가 낸 주소는 OS 안으로 가는데 그 주소를 한 번 읽어 frame number를 알아낸 뒤, 해당 frame number의 주소를 또 읽어야 해서 속도가 두 배로 느림
  3. TLB(Translation Look-aside Buffer)로 page table 만들기
    • 주소 변환을 목적으로 별도의 SRAM 칩으로 만듦
    • 원리는 cash memory와 비슷
    • CPU보다는 느리지만 보다 많은 entry 저장 가능
    • CPU와 memory의 중간 성격
    • Effective Memory Access Time(유효 메모리 접근 시간)
      → CPU가 주소를 내고, 메모리의 내용을 읽어오는데 걸리는 시간
      → Tm: 메모리 내용을 읽는데 걸리는 시간
      Tb: buffer를 읽는데 걸리는 시간
      hit ratio(h): 주소에 해당하는 page table entry가 buffer에 존재할 확률
      (buffer의 크기는 충분히 크지 않아서 entry 중 일부만 buffer에 있고 나머지는 memory에 존재)
      (★ 중요 예제 ★)
      Tm: 100ns, Tb: 20ns, hit ratio(h): 80% 일때, Teff=?
      sol.) h(Tb+Tm) + (1-h)(Tb+Tm+Tm)
      = (0.8*120ns) + (0.2)(220ns)
      = 140ns
      → Tm: 100ns인데 40%의 손실이 발생한 결과임
      → 하지만, 실제 hit ratio는 95%이상이므로 손실은 아주 작음