[운영체제-양희재 교수님]20-21강 연속 메모리 할당과 페이징

경성대학교 양희재 교수님의 운영체제 20강

경성대학교 양희재 교수님의 운영체제 21강

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

• 다중 프로그래밍 환경
  • 부팅 직후 메모리 상태 ⇒ OS + big single hole(OS 이외의 빈 공간)
  • 프로세스 생성과 종료 반복 ⇒ scattered holes(종료된 프로세스가 남긴 공간)
• 메모리 단편화(Memory fragmentation)
  • Hole이 불연속적으로 흩어져 있기 때문에 프로세스 적재 불가 ⇒ 외부 단편화(external fragmentation) 발생

연속 메모리 할당 방식

• 외부 단편화를 최소화하기 위해 할당 방식 고안
  • First-fit(최초 적합): 들어갈 수 있는 공간 중 제일 처음 만나는 위치에 할당
  • Best-fit(최적 적합): 들어갈 수 있는 공간 중 가장 차이가 적은 위치에 할당
  • Worst-fit(최악 적합): 들어갈 수 있는 공간 중 가장 차이가 큰 위치에 할당
• 할당 방식에 따른 성능 비교
  • 속도 기준 ⇒ first-fit
    • 처음 만나는 지점에 할당하니 가장 빠르다.
  • 이용률 기준 ⇒ first-fit, best-fit
• 할당 방식을 바꾸어도 외부 단편화로 인해 전체 메모리의 약 1/3을 사용 불가 ⇒ 다른 방법 필요

Compaction

• 앞서 살펴본 메모리 할당 방식으로도 막지 못하는 낭비를 없애기 위한 방법
• 불연속적으로 흩어진 hole을 모두 한곳으로 모으는 작업 ⇒ 고부담
• Hole을 모으는 데 사용될 최적의 알고리즘 부재

페이징(Paging)

• 프로세스를 메모리에 연속으로 할당하지 말자.
• 프로세스를 일정 크기로 잘라서 메모리에 할당
  • 프로세스를 자른 것 ⇒ 페이지(page)
  • 메모리를 자른 것 ⇒ 프레임(frame)
  • 페이지의 크기 = 프레임의 크기
• 프로세스가 잘렸는데도 정상 작동되는가?
  • 프로세스는 메모리에 연속적으로 할당되어 있어야 한다. 따라서 CPU를 속여야 한다.
  • MMU에 relocation Register를 여러 개를 두고 레지스터 값을 바꿈 ⇒ CPU 입장에선 메모리에 연속으로 할당된 것처럼 보임
  • Logical address는 연속적이고 physical address는 불연속적으로 된다.
• 페이지 테이블(page table)
  • 페이징을 위해 페이지 단위로 사용하는 MMU
  • 재배치 레지스터가 여러 개 존재

주소 변환(Address Translation)

• 논리 주소
  • CPU가 내는 주소
  • 2진수로 표현
  • 주소가 전체 m 비트라고 가정할 때,
    • 하위 n 비트 ⇒ 오프셋(offset) 또는 변위(displacement)
      • m = 2^d
    • 상위 m-n 비트 ⇒ 페이지 번호(p)
• 논리 주소 → 물리 주소 변환
  • 페이지 번호 p ⇒ 페이지 테이블의 인덱스 값
  • p에 해당하는 페이지 테이블 내용 ⇒ 프레임 번호 f
  • p는 f로 바뀌며 변위 d는 변하지 않음

예제

• Page size가 4 bytes이고 Page Table이 5 6 1 2 순으로 구성된 상황에서 논리 주소 13번지를 물리 주소로 변환
  • 논리 주소 13번지 ⇒ 1101
  • Page size가 2² bytes ⇒ d = 2 ⇒ 하위 2 비트(01)는 변위
  • 나머지 상위 비트(11)는 페이지 테이블의 인덱스 값 ⇒ 3
  • 3에 해당하는 프레임 번호 ⇒ 2 ⇒ 10
  • 최종 물리 주소는 1001 ⇒ 9번지
• Page Size가 1 KB이고 Page Table이 1 2 5 4 8 3 0 6 순으로 구성된 상황에서 논리 주소 3000번지를 물리 주소로 변환
  • 논리 주소 3000번지 ⇒ 101110111000
  • Page size가 2¹⁰ bytes ⇒ d = 10 ⇒ 하위 10 비트(1110111000)는 변위
  • 나머지 상위 비트(10)는 페이지 테이블의 인덱스 값 ⇒ 2
  • 2에 해당하는 프레임 번호 ⇒ 5 ⇒ 101
  • 최종 물리 주소는 1011110111000
• Page Size가 1 KB이고 Page Table이 1 2 5 4 8 3 0 6 순으로 구성된 상황에서 물리 주소 0x1A53 번지를 논리주소로 변환
  • 물리 주소 0x1A53 ⇒ 1101001010011
  • Page size가 2¹⁰ bytes ⇒ d = 10 ⇒ 하위 10 비트(1001010011)는 변위
  • 나머지 상위 비트(110)는 프레임 번호 ⇒ 6
  • 6에 해당하는 페이지 테이블의 인덱스 값 ⇒ 7 ⇒ 111
  • 최종 논리 주소는 1111001010011 ⇒ 0x1E53

내부 단편화(Internal Fragmentation)

• 프로세스 크기가 페이지 크기의 배수가 아닌 경우 발생
  • 마지막 페이지는 한 프레임을 다 채울 수 없음
  • 페이지 내부에 남은 공간만큼 메모리 낭비
• 내부 단편화로 인해 낭비되는 최대 메모리 크기 = 페이지 크기 - 1 byte
  • 낭비되는 크기가 작기 때문에 큰 문제가 되지는 않는다.

페이지 테이블 만들기

• CPU 레지스터
  • MMU를 CPU의 기억장치인 레지스터로 만들 수 있다.
  • 장점) 주소 변환 속도가 빠르다.
  • 단점) 큰 페이지 테이블은 들어갈 수 없다.
• 메모리로 만드는 법
  • 메모리 내부에 MMU를 넣을 수 있다.
  • 장점) 큰 페이지 테이블도 들어갈 수 있다.
  • 단점) 페이지 테이블을 먼저 읽어야 하므로 과정이 2배가 되어 주소 변환 속도가 느리다.

TLB(Translation Look-aside Buffer)

• TLB: 주소 변환 목적으로 사용하는 high speed SRAM
  • 참고) 캐시 메모리는 SRAM으로 만든다.
• TLB를 사용하면
  • CPU 레지스터보다 변환 속도가 느리지만 테이블 엔트리 개수를 많이 넣을 수 있고
  • 메모리보다 변환 속도는 빠르지만 더 적은 수의 테이블 엔트리를 넣을 수 있다.
• 유효 메모리 접근 시간 = (Tm + Tb) + (1 - hit ratio)(Tb + Tm + Tm)
  • 유효 메모리 접근 시간: 메모리에서 읽어오는 데 걸리는 시간
  • Tm: 메모리를 읽는 시간
  • Tb: 버퍼를 읽는 시간
  • hit ratio: 읽고자 하는 내용이 테이블에 존재하는 확률
  • Miss되는 경우(1 - hit ratio) 메모리에서 찾은 뒤 해당 주소에 다시 가야 하므로 Tm의 시간이 추가로 소요된다.

보호와 공유

• 보호(Protection)
  • 모든 주소는 페이지 테이블을 경유 ⇒ 페이지 테이블 엔트리마다 r, w, x 비트를 두어 해당 페이지에 대한 접근 제어 가능
    • 할 수 없는 작업을 하려고 시도하면 인터럽트 발생 ⇒ 강제 종료
  • 해킹 등 방지 가능
• 공유(Sharing)
  • 같은 프로그램을 쓰는 복수 개의 프로세스가 있는 경우 code를 공유 가능 ⇒ 프로세스의 페이지 테이블에서 코드 영역이 같은 곳을 가리키게 한다.
    • 단, 실행 중 자신의 code를 바꾸지 않는 non-self- modifying code(reentrant code, pure code)인 경우에만 가능
  • 메모리 낭비 방지 가능