연속 메모리 할당(Contiguous Memory Allocation)과 페이징(Paging)

개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.
경성대학교 양희재 교수님 수업 영상을 듣고 정리하였습니다.

다중 프로그래밍 환경에서...

• 부팅 직후 메모리 상태: O/S + big single hole

• 프로세스 생성 & 종료 반복 -> scattered holes(쪼개져있는 holes)

• 메모리의 단편화(Memory fragmentation):hole들이 떨어져있음

  • Hole들이 불연속하게 흩어져 있기 때문에 프로세스 적재 불가
  • 외부 단편화(extend fragmentation)발생: 홀들이 연속되어져있지 않고 떨어져 있음
    
    -> 흩어져 있는 메모리를 합쳐서 사용하면 새 프로세스를 올릴 수 있는데 연속되어 있지 않아 올릴 수 없는 불편함 존재(낭비)
  • 외부 단편화를 최소화 하려면?

외부 단편화를 최소화 하려면? = 연속 메모리 할당

• First-fit(최초 적합): 메모리를 순차적으로 찾아 제일먼저 발견되는 곳에 넣는 것
• Best-fit(최적 적합): 제일 사이즈가 밀접한 곳에 넣는 것
• Worst-fit(최악 적합): 크기가 제일 안맞는 곳에 넣는 것

예) hole: 100/500/600/300/200 KB | 프로세스: 212 417 112 426 KB

• First-fit(최초 적합): 426은 넣을곳이 없음(외부 단편화)
• Best-fit(최적 적합): 다 넣을 수 있음(메모리를 제일 잘 사용한 방법)
• Worst-fit(최악 적합): 여전히 426은 들어가지 못함

할당 방식 성능 비교: 속도 및 메모리 이용률

• 속도면에서는 first-fit이 좋다 -> 제일 먼저 나오는곳에 넣으면 되니까
• 이용률: first-fit, best-fit -> 메모리가 얼마나 잘 이용되는가를 비교하자면 둘은 거의 비슷하게 나온다.

그러나 best-fit을 사용했음에도 불구하고 외부 단편화로 인한 메모리 낭비는 존재: 메모리의 1/3수준은 여전히 사용불가 수준

• Compaction: 메모리에 흩어진 hole들을 하나로 모은다. 최적 알고리즘 없음, 고부담(홀을 옮길지, 프로세스를 옮길지, 그 크기에 따라 굉장히 복잡함)
• 다른 방법은? Paging

페이징(Paging)

프로세스를 일정크기(=페이지)로 잘라서 메모리에 넣는다. (메모리를 일정한 단위로 잘라서 홀 안에 넣는다.)

• 프로세스는 페이지(page)의 집합
• 메모리는 프레임(frame)의 집합
• page의 사이즈와 frame의 사이즈는 똑같다. (해당 page는 각각의 frame에 들어가야 하니까)

페이지를 프레임에 할당한다

• MMU내의 Relocation register값을 바꿈으로써 cpu는 프로세스가 연속된 메모리 공간에 위치한다고 생각하게 한다.
• MMU는 페이지테이블(page table)이 된다.

일반적으로 프로세스를 잘라서 넣으면 프로그램은 실행이 되지 않는다. 이를 실행하기 위해서는 cpu를 속여야 한다.

cpu에 Relocation register를 여러개를 둠으로써 cpu는 연속으로 주소를 보냈다고 생각하지만, mmu를 거칠적에는 새로 연산을 해주게된다(다른 값을 내준다)
cpu는 여전히 메모리에 연속적으로 들어갔다고 생각하지만 실제 메모리에는 막 들어가져있다(다른 곳에 매핑 될 수 있도록 해준다)

사실은 메모리 전체를 처음부터 일정크기로 나눈다. 그리고 프로세스를 올릴 적에도 그냥 연속해서 올리는게 아니라 여러개의 페이지로 쪼개 올린다. 흩어져 잇음에도 불구하고 cpu를 속여 mmu값을 적절하게 넣어 연속적이게 보이도록 해준다.
logical address는 연속, physical address는 불연속

이를 통해 메모리의 외부단편화 문제를 해결할 수 있게 된다.

페이징에서의 주소 변환(Address Translation)

• 논리주소(Logical address): cpu가 내는 주소
  • cpu가 내는 주소는 2진수로 표현(전체 m비트)
  • 하위 n비트는 오프셋(offset)또는 변위(displacement, d)
  • 상위 m-n비트는 페이지 번호(p)

이 전체중에 n을 몇비트로 할것인가는 페이지 사이즈를 얼마로 하는가에 따라 달라진다.

한 페이지 사이즈가 16byte라고 한다면 16byte단위로 자른다는것. 그렇다면 하위 n비트에 주어지는것은 4(2의 4승=16byte)비트이다.

• 주소변환: 논리주소 -> 물리주소(Physical address)
  • 페이지번호(p)는 페이지 테이블 인덱스 값(p=m-n)
  • p에 해당되는 테이블 내용이 프레임 번호(f)
  • 변위(d)는 변하지 않음

예제1) 논리주소 13번지는 물리주소 몇번지일까?

• page size = 4bytes
• page table: 5 6 1 2

예제2) 논리주소 3000번지는 물리주소 몇번지일까? & 물리주소 0x1A53번지는 논리주소 몇번지일까?

• page size = 1KB
• page table: 1 2 5 4 8 3 0 6

내부단편화, 페이지 테이블

• 내부단편화(Internal Fragmentation): 프로세스 크기가 페이지 크기의 배수가 아니라면, 마지막 페이지는 한 프레임을 다 채울 수 없다.
• 남는공간 ≠ 메모리공간

한 페이지의 사이즈는 4byte이고 프로세스의 크게는 15byte라고 하자. 그러면 4개의 페이지가 필요할 것이다.
즉 3번째 페이지는 전체를 다 채우지못하고 1이 남게될 것이다. 4의 배수가 아니니 한 프레임을 다 채울 수 없다. 이 1byte는 누구도 쓸 수 없는 영역이다.

이 또한 메모리의 낭비 이고 이런 경우를 내부단편화라고 한다.

-> 내부단편화의 크기는 미미하다. 크기의 최대 = 페이지사이즈 - 1byte

페이지 테이블 만들기

• CPU 레지스터로 만든다면?
  • 장점: 주소변환이 빠르다.
  • 단점: 많은 양이 들어가지 못한다.
• 메인 메모리로 만든다면?
  • 장점: 많은 양을 넣을 수 있다.
  • 단점: 주소변환이 느리다.

둘다 가능한 방법이지만, 현실적으로 사용하기에는 무리가 많다.

• TLB(Translation Look-aside Buffer): 별도의 s램 칩으로 만든다.

캐시메모리로 만든다. 메인메모리는 d램으로 만들어서 속도가 느린데, 캐시메모리는 s램으로 만들어서 속도가 빠르다.
s램으로 만드는데 캐시는 메인메모리에 있는애를 빨리 가져와서 접근하도록 하는데, 우리는 지금 주소변환을 위한 목적으로 만든것으로
이를 캐시라 하지않고 페이지테이블 목적으로 하이스피드 s램을 사용한것을 TLB라고 한다. 원리는 캐시메모리와 비슷하다.

cpu와 메모리 그 사이에 있는 TLB!

• 관점: 테이블 엔트리 개수 vs 변환 속도

• 연습> TLB사용 시 유효 메모리 접근 시간(Effective Memory Access Times)

  • 메모리에서 어떤 내용을 읽어오는데 걸리는 유효한 시간
  • Tm메모리를 읽는데 걸리는 시간 = 100ns, Tb look-aside Buffer를 읽는 시간=20ns, hit ratio=80%
  • h(Tb+Tm) + (1-h)(Tb+Tm+Tm) = 0.8(20+100) + 0.2(20+100+100) = 140ns

보호와 공유

보호(Protection): 해킹 등 방지
모든 주소는 페이지 테이블을 경유하므로, 페이지 테이블 엔트리마다 r,w,x 비트를 두어 해당 페이지에 대한 접근 제어 가능하다.

비트니까 0또는 1의 값을 가질 수 있을 것이고, 만약 r비트가 0인데 내용을 고치고 싶다고 하자.
그러면 page table에서 cpu에 interrupt가 가고, 그러면 cpu는 하던일을 중단하고 os의 특정 routine으로 가서 잘못된 행위를 하려는 프로세스를 강제로 종료시킨다.

이런 방식으로 해킹을 방지한다.

더 나아가, 어짜피 cpu가 내는 모든 주소는 page table을 경유하기 때문에 r,w,x비트를 두어 해당 페이지에 대한 접근 제어가 가능하다.
os가 설정해둔 권한 바깥의 일을 하려고 한다면, 인터럽트를 강제로 걸도록하여 막을 수 있다.

공유(Sharing): 메모리 낭비 방지
같은 프로그램을 쓰는 복수 개의 프로세스가 있다면 Code + data + stack에서 code는 공유가능

(단, non-self-modifying code = reentrant code(재 진입 가능 코드) = pure code인 경우) 프로세스의 페이지 테이블 코드 영역이 같은 곳을 가리키게 되어있다.

code 영역은 안바뀌고 data 영역만 변경된다. (data는 context switching이 이루어지지만 code는 같은곳을 가리킨다.)