16. 외부 단편화와 페이징

 

연속 메모리 할당

 

 

부팅 후에 OS가 먼저 메인 메모리로 올라온 상황을 생각해보자.

 

이때 메인 메모리 올라온 프로그램은 없는 상태임으로 하나의 큰 Hole이라고 생각하자.

 

 

이후 프로그램을 실행할 텐데 p1 p2 p3 p4 등 프로세스들이 메인 메모리에 올라올 것

 

이고 이 후 p2가 끝났다고 가정하면 다음과 같은 상태가 된다.

 

 

이처럼 프로세스가 생성되고 종료되면서 많은 Hole들이 흩어지게 될 것이다.

 

이런 식으로 쪼개져있는 것을 메모리 단편화(fragment)라고 한다.

 

 

 

 

 

 

이렇게 Hole 들이 많아지면 문제가 뭘까? 예를 들어 130 Kbyte에 프로그램을 메모리에 올리려고 한다.

 

홀에 있는 공간은 합치면 170 Kbyte ( 110 + 40 + 20 )으로 충분히 들어갈 수 있지만 흩어져 있기 때문에 130 Kbyte를

 

올릴 수 있는 공간이 없다. 따라서 적재될 수 없는 것. 이러한 것을 외부 단편화 라고 한다.

 

즉 합치면 충분히 들어갈 수 있지만 떨어져 있기에 못 들어가는 것을 외부 단편화라고 알아두자.

 

 

 

외부 단편화를 어떻게 최소화할 수 있을까?

 

연속 메모리 할당 방식

• first-fit ( 최초 적합 )
• Best-fit ( 최적 적합 )
• Worst-fit ( 최악 적합 )

다음과 같은 예로 한번 알아보자 . 

 

 

1. first-fit

 

메모리를 순차적으로 찾은후에 제일 먼저 발견되는 곳에 넣는 것을 최초 적합 (first- fit)이라고 한다.

 

위에서부터 순차적으로 찾는다면 프로그램은 hole 1로 들어가게 된다.

 

2. Best-fit

 

프로그램에 사이즈와 가장 밀접한 가까운 사이즈의 메모리에 넣는 것

 

50은 작으니 들어갈수 없고 가장 가까운 80인 hole2에 들어가게 될 것이다.

 

3. Worst-fit

 

가장 공간이 많이 남는 사이즈의 메모리에 넣는 것

 

 

 

메모리는 프로세스가 실행과 종료를 반복하면서 hole들이 떨어지는 형태로

 

바뀌게 된다. 일반적인 할당 방식 간의 속도 및 메모리 이용률을 보면

 

속도는 first-fit 이 어디에 넣을지 비교하지 않으니 빠르고

 

이용률 즉 메모리 이용률에 대해서는 first-fit과 best-fit이 좋다고 알려져 있다.

 

따라서 first 나 best fit 방식을 쓰자.

 

 

외부 단편화 해결 방법?

 

best-fit 방식을 하더라도 외부 단편화로 인한 문제가 없어지는 것은 아니다. 

 

따라서 해결방법이 필요한데 한 가지 해결방법은 Compaction이다.

 

OS가 hole들을 하나로 모으는 것인데 메모리를 움직여야 하는 고부담이 있게 된다.

 

따라서 실제로는 힘든 방법에 속한다.

 

또 다른 방법은 메모리를 효과적으로 사용하는 방법인 Paging이다.

 

앞 서 예제에서 홀들을 모으면 총 170 kbyte로 130 kbyte를 올릴 수 있지만 그러기엔 부담이

 

너무 크다고 하였다. 따라서 프로그램을 쪼개면 어떨까?

 

 

프로세스는 항상 연속해서 들어간다고 생각했지만 연속 안 하면 안 될까? 즉 130 Kbyte를 쪼개서 들어간다면

 

충분히 가능할 것이다. 자를 적에는 일정한 단위로 잘라야 하는데 예를 들면 10 Kbyte 단위로 자른다면

 

13개가 나올 것이다.  Hole들도 마찬가지로 페이징 단위로 자른다.

 

 

그런데 프로그램을 잘라서 넣는데 실행이 될까? 돌 수 있을까? 잘라서도 돌 수 있게 하려면

 

CPU를 속여야 한다. 앞 서 말했듯 CPU가 알고 있는 주소는 MMU를 거치면서 CPU가 알고 있는 주소와 다르게

 

실제로 배치된다고 말하였다. 130 Kbyte의 10 Kbyte 단위라면 13개의 mmu의 relocation Register을 두어서 CPU는 메모

 

리가 연속적으로 들어있다고 믿게 하는 것이다.

 

정리하자면 프로세스(프로그램)를 일정 크기로 자른 것을 페이지라고 부른다.

 

메모리도 단위로 자른다고 했는데 메모리를 자른 것을 프레임이라고 부른다

 

즉 페이지와 프레임의 단위는 같을 수밖에 없다. 단지 용어의 차이다.

 

우리는 이런 목적으로 사용하는 mmu를 Relocation register가 table 형식으로 들어있고 페이지 단위로

 

자르니 Page Table이라고 부른다.

 

이렇게 페이징을 이용해서 외부 단편화 문제를 모두 해결할 수 있다.

 

CPU가 내는 주소 

• 논리 주소 : Logical Address

주소 변환 : 논리 주소 -> 물리 주소 ( Physical address )

CPU가 내는 주소는 0과 1 이진수를 쓴다. 

 

cpu가 내는 주소를 m개의 비트로 되어있다고 하자.

 

이 주소중 m-n 은 P 페이징 넘버 ( 페이지 테이블의 인덱스 ) 에 n을 d ( 변위 , 오프셋, 몇 번째에 떨어져 있는지 )에 쓰게

 

된다.

 

그러면 전체 주소중 n을 몇 비트로 해야 하는지는 페이지 단위에 따라 다르다.

 

예를 들어 한 페이지 사이즈가 16byte라고 해보자. 16byte는 2의 4승이다.

 

따라서 한 페이지를 16바이트로 두면 n 값은 4비트가 된다.

 

페이지 사이즈가 1KB 라면 2^10 byte이므로 10비트가 n이 된다.

 

 

 

주소 변환은 어떻게 될까?

 

CPU가 어떤 주소를 내었는데 그 주소가 50번지라고 해보자. 그러면 그 주소는

 

메인 메모리에 몇 번지에 해당될까

 

 

우선 10진수 50은 110010이다. 우리는 한 페이지가 16바이트라고 했으니

 

P는 11 // D는 0010 (4비트)가 되겠다.

 

이진수로 11은 십진수로 3이다. 그렇다면 Page Table에 3번째 인덱스로 가게 된다.

 

3번째 인덱스의 값이 8이라고 해보자.  그러면 실제 메인 메모리에 주소는

 

 1000 // 0010 이 가게 된다. 즉 CPU가 내는 50번지 논리 주소는 실제 메모리에 130번지에

 

해당한다. 즉 8번째 프레임에 시작 주소 128번지에 2만큼 떨어져 있게 된다.

 

CPu는 속은 것이다. 50번지에 있다고 생각하지만 실제로는 (128 + 2) 130번지에 있는 것

 

논리주소 : 50번지 물리주소 : 130번지

 

 

 

 

 

 

 

이제 페이지 단뒤로 잘라진 프로그램은 메모리에 어느 곳에나 올려도 상관없다.

 

잘라진 페이지의 수만큼(3개) 페이지 테이블 인덱스를 만들고 페이지 테이블의 주소를 프레임 번호로 주면

 

된다.

 

CPU는 프로세스가 연속된 메모리 공간에 있다고 착각하고 메모리상에 실제로는 떨어져 있으니

 

외부 단편화는 일어나지 않고 모든 문제가 해결되게 되는 것이다.