[운영체제및실습]12주차 2회차: 페이징

이번시간에는 페이징에 대해서 학습하도록 하겠습니다.

가변동적 메모리 할당 방법인 다이내믹 파티션 방법을 복습해봅시다. 

이것은 fixed partioning이라는 고정 분할 방법에서 발전된 것이라고 했습니다.

가변 동적 메모리 할당을 할 떄 문제점은 extenal fragmentation이라고 해서 프로세스에 속하지 않은 작은 메모리 조각들이 생기는 문제들이었습니다. 6M, 4M, 6M 빈공간이 있는데 이 공간을 합치면 16M가 됩니다. 그런데 조각나 있어서 16M 프로세스를 집어넣을 공간이 없습니다. 합치면 되지만 지금은 쪼개져 있어서 문제입니다. 이런 문제를 해결하기 위해 컴팩션이라고 해서 프로세스를 이동시켜서 빈 메모리를 한 곳으로 모으면 되는데, 시간이 많이 걸려서 좋은 방법이 아닙니다. 흩어져 있는 작은 조각들의 메모리인 fragmentation을 쓰는 방법을 해결하기 위해서 나온 방법이 페이징 방법입니다.

 

1. 페이징

페이징 정의

페이징 방법은 과거 기술에 비해 혁신적인 메모리 할당 방법입니다. 페이징에서는 페이지라고 불리는 일정한 크기의 조각들로 프로세스를 조각내는 것입니다.

 

우리가 전에 가상 주소 공간을 배울 때, 페이지라는 용어를 잠깐 나왔었습니다. code, data, stack영역처럼 프로세스의 전체 공간을 일정한 크기의 조각으로 나누었는데 그것이 page입니다. 마치 집을 지을 떄 벽돌을 쌓아서 짓듯이 똑같은 크기의 메모리 조각으로 프로세스를 나눈 것입니다. 조각 단위로 메모리에 갖다 넣자는 것이 페이징 방법의 핵심입니다. 

 

frame size = page size = disk block size

프로세스를 페이지라는 조각을 냅니다. 그리고 메인 메모리도 (page) frame 조각으로 메인 메모리 분할을 냅니다. 페이지 크기는 4KB입니다. 디스크에서 한 블록의 사이즈가 4KB인데, 블록 사이즈와 페이지 사이지와 프레임 사이즈를 다 같게 잡습니다. 

일정한 크기로 나누는 것이 고정 분할식이었습니다. 거기에서 이용되었던 개념을 페이징 방법에서 계승해서 페이징 방법이 나타난 것입니다. 차이점은 고정 분할 식에서는 메모리가 일정한 크기로 나뉘어진 것에 프로세스가 전체가 한 메모리 조각에 들어갔지만, 페이징에서는 프로세스보다 작은 크기인 페이지 프레임이라는 단위로 메모리를 나눴기 때문에 한 프로세스가 여러 개의 페이지로 나뉘어서 메모리에 들어간다는 차이가 있습니다.

---

2. Assignment of Process Pages to Free Frames

페이지를 이제 식별을 해야 합니다. 프로세스를 페이지 단위로 나누면 페이지를 각 조각들을 식별하기 위해 번호를 붙입니다.

메모리 옆의 번호는 페이지 번호입니다.

 

프로세스 각각마다 페이지 번호를 매겨 조각을 나누어서 프로세스들이 페이지로 나뉘어서 각 페이지들이 메모리 프레임에 들어간 모습입니다. 메모리 시작 쪽에는 os가 있는데, 여기서는 메모리 프로세스들만 표현되었습니다. b가 끝나면, b를 os가 전부 회수할 것입니다. 4~6은 메모리 프레임이 비어있습니다. 프로세스 d가 실행되었다고 합시다. 이전에 가변 동적 할당방법에서는 5개짜리 페이지로 구성되는 프로세스가 이 안에 못 들어갔었습니다. 5개의 페이지가 뭉쳐서 마치 하나처럼 해서 들어가야 했었습니다. 그런데, 여기서는 프로세스를 쪼개어서 메인 메모리에 저장합니다. D가 시작부터 끝까지 연이어서 메모리에 저장되는 것이 아니라 흩어져있습니다. (b)에서 컴팩션을 해서 c를 위로 옮기면, 5개를 연이어서 할 수 있으나 시간이 오래 걸려 사용하지 않습니다. 

external fragmentation이 바로 (f)처럼 프로세스 외부에 작은 공간이 생기는 것이었는데, 이제는 집어넣을 수 있는 만큼 집어넣을 수 있게 되었습니다. 작은 조각이 남아도 이제 걱정이 안 되는 것입니다. 그래서 페이징 방법 사용으로 인해 external fragmentation이 발생하지 않게됩니다.

 

페이징은 메모리를 효율적으로 쓸 수 있어서 혁신적인 방법입니다. 대신 internal fragmentation이 발생합니다. 프로세스에게 할당된 공간 안에서 안 쓰고 남는 것입니다. 예를 들어, 네 개의 프레임을 받았는데, 4K 4개이므로 16KB를 할당 받은 것입니다. 프로세스 C는 13KB, 15KB일 수도 있습니다. 12KB보다는 클 것입니다. 그렇게 되면 4K바이트 미만의 크기의 internal fragmentation이 생길 수 있는데, 신경쓰지 않습니다.

 

오버헤드라는 것은 어떤 효과를 얻기 위해서 치뤄야 될 대가입니다. 실행시간이 길어진다거나 메모리를 더 차지한다거나 등입니다. 부수적인 비용을 오버헤드라고 합니다. 

 

(f)에서 프로세스 D의 경우는 4~6에 3개가 저장되어있고, 11~12에 2개가 저장되어있습니다. 서로 연속적으로 엑세스할 수 있어야 합니다. 

 

3. Page Table

Page Table이라는 기술을 생각해냈습니다. 페이지 테이블에 대해 아주 잘 알고 있어야 합니다!!!!!!!!!!!!!!!!!!!!!!!!!!!!

 

실제로 운영체제의 메모리 관리는 요즘 운영체제에서 페이징을 이용하기 때문에 거의 80%는 페이지 테이블과 관련된 것이어서 메모리 관리는 거의 대부분 이해할 수 있습니다. 페이지 테이블은 각 프로세스마다 하나씩 페이지 테이블을 하나씩 만듭니다. 각 프로세스마다 만들기 때문에 프로세스에 의존적인 고유한 정보이기 때문에 PCB에 저장합니다. 

 

각 프로세스 page table 옆에있는 번호들은 page #(page number)입니다. 그리고 page table 안에 있는 번호는 frame #(frame number)입니다. page number는 page table의 인덱스이기 때문에 따로 저장하지 않습니다. page table 안의 번호가 역으로 있어도 됩니다. 맨 오른쪽은 Free frame list로 운영체제 파일 시스템의 슈퍼 블록에 저장되는 정보입니다. 페이징 방법을 쓰면, 슈퍼 블록에도 이런 식으로 프레임 번호만 알면 되는 것입니다. 그리고 특이한 것이 프로세스 B인 경우 NNN이 들어가 있는데 이것은 NO 또는 Null이라는 것입니다. 즉, 페이지가 메모리에 없다는 의미입니다. 그럼 프로세스 B가 있으니까 프로세스 B가 끝나서 없어진 상황은 아닙니다. 프로세스 B가 끝나서 없어진 상황은 아닙니다. 프로세스 B가 완전히 끝나서 없어졌다고 하면, 페이지 테이블이 완전히 지워져 버립니다. 그런데 현 상황에서 페이지 테이블이 남아있는 상태에서 다만, 유저 컨텍스트에 있던 것이 메모리에 안 들어와있다는 것이니까 프로세스 B가 보조기억장치 안의 가상 주소 공간에 나가있는 상태이고, swap out상태이며, 메모리에는 없는 상태입니다. 즉, 프로세스 B는 suspended 상태인 것입니다.

다이내믹 파티션에서는 빈 메모리를 나타내기 위해 일일이 테이블로 몇 번지에서부터 몇 바이트가 비어있다고 기다란 테이블을 유지해야 했어서 찾는데 시간이 많이 걸리는데, 여기서 페이징 방법에서는 그냥 메모리 프레임 번호만 알고 있으면 되기 때문에 빈 메모리를 찾는데 매우 빠릅니다. 메모리를 일정한 크기로 조각을 내서 그 번호만 알면 되는 것입니다.

 

4. Page Number and Offset(1)

페이징 방법을 쓰면, 페이지 테이블을 계속 가지고 있어야 하는 단점이 있으며, 또 하나는 메모리의 주소가 두 부분으로 구성되는 특징이 있습니다. logical memory address가 페이징 방법을 쓰면, page number와 offset within the page로 바뀌어야 합니다. offset은 한 페이지 안의 위치를 나타낸 것입니다. 4KB 내에서 0번째 바이트~4095바이트 중 얼마만큼 떨어져 있는지 나타내는 정보입니다. 

 

그림을 보면, 왼쪽 상단의 것이 페이징을 쓰기 전의 프로세스의 상대적 주소입니다. Relative address =1502므로, 프로세스 시작에서부터 1502바이트만큼 떨어져 있는 위치라는 것을 나타냅니다. 예를 들어, 1502바이트에 있던 것이 변수라던가, 점프를 한다던가 1502번지라는 것이며, 프로세스 0번지, 1번지 등등 바이트마다 주소를 매기는데, 1502번째 바이트 위치라는 것입니다. 그 위치가 바로 여기라고 그림에서 표시가 되어있습니다. 여기 바이너리 번호는 십진수를 이진수로 표현한 것입니다. 이것이 페이징 방법을 쓰기 전에 프로세스의 logical address를 나타낸 것인데, 오른쪽은 페이징을 쓰는 컴퓨터에서 주소체계를 보인 것입니다. 페이징 사이즈가 1KB라고  가정했습니다. 요즘 운영체제에서는 4K이지만, 설명간단히 하기 위함입니다. 페이지 단위로 프로세스가 나뉘기 때문에 1K=1024B여서 페이지마다 1024조각을 낸 것입니다. 그러면 1024B 두 개면, 2048B입니다. 그런데 지금 프로세스는 2700B로 1024바이트보다 큽니다. 그래서 3개의 조각이 나는데, 세 번쨰 페이징 조각 중 안 쓰는 조각이 존재합니다. 이 부분은 internal fragmentation이라는 프로세스 내의 안 쓰는 조각이 됩니다. 페이징 방법을 이용하든 안 하든, 똑같이 액세스 하려는 부분은 같아야 합니다. 그래서 페이징 방법을 쓰기 전에는 프로세스 시작에서부터 1502바이트로 떨어진 곳으로 가면 되지만, 페이징에서는 조각으로 나뉘기 때문에 몇 번 페이지에서 몇 바이트 떨어진 곳이라고 표현해야 합니다. 아파트 동 수가 10개이면, 주소를 매길 때, 1동의 몇 호라고 매기지, 전체를 일련번호로 매기지 않습니다. 그럼 몇 동에 있는지 알게 쉽게 하기 위해서 몇 번 조각이고, 몇 번 조각에서 얼마만큼 떨어져 있다라고 주소 지정을 해야 합니다. 그래서 붉은 지점은 Page 1에서 428B(1502-1024=478)만큼 떨어져있어서 Logical address = Page# = 1, offset = 478가 됩니다. 

 

5. Page Number and Offset(2)

상대적인 주소라는 Relative address랑 Paging에서의 주소 관계를 설명하겠습니다. 8비트 어드레스 컴퓨터를 생각해봅시다. 주소가 8비트이기 때문에 그 주소값의 최솟값은 0000 0000으로 표현되는 0이며, 그다음은 1씩 증가하여 0000 0001이 됩니다. 제일 큰 주소 값은 8비트가 모두 1 인 1111 1111로 255입니다. 바이너리로 보도록 합시다. 8비트 주소체계에서 page size = 16B라고 가정합시다. 페이징 한 조각이 16B라는 것입니다. 바이트 단위로 주소를 매기므로, 페이지 내에서 서로 다른 주소가 16개 있는 것입니다. 노란색 박스가 하나의 페이지가 되는 것입니다. 16=2^4이므로 4비트가 필요해서 offset은 4비트가 되야 하며, 0000~1111까지입니다. 0~15주소까지는 앞에 있는 4비트가 전부 0000입니다. 뒤의 4비트는 0000~1111입니다. 0000이라는 페이지 내에서 0000~1111로 가다가 offset을 십진수로 표현하면, 0~15가 되는데, 더 이상 다른 바이트가 없습니다. 그래서 그다음 페이지로 가서 주소를 지정하게 됩니다. 

즉, 페이지 사이즈를 보고, 몇 비트를 offset으로 써야 하는지를 결정합니다. 페이지 사이즈가 16 bytes여서 서로 다른 주소 16개가 되므로, 주소 지정을 위한 주소 비트가 4비트 필요합니다. 

 

6. Address Traslation in Paging

이 그림에서는 16비트 컴퓨터를 예로 들었습니다. 앞의 Page NUmber and Offset(1)에서 왼쪽 그림에서 보았듯이 주소 비트가 16비트가 됩니다. logical address가 1502인데, 그런 경우의 Page# = 1, Offset = 478입니다.  여기서도 보인 것처럼 바이너리 비트가 왼쪽, 오른쪽 동일한데, 두조각으로 나뉘어져 있습니다. 몇 비트 분할해야 하냐면, offset이 몇 비트 필요한지 잡는 것입니다. page size = 1K = 1024B이므로 한 페이지 내에서 1024개의 바이트가 존재하므로 각 바이트 단위로 주소 지정을 하려면, 1024개의 주소가 있어야 합니다. 1024=2^10이므로 10비트가 주소비트로 표현됩니다. 아래에서 10비트로 잡은 것이 offset이며, 남은 비트가 몇 비트든 나머지 비트가 페이지 번호 비트가 됩니다. 

 

그래서 page size = 1K일 때, 16비트 컴퓨터에서 실제로 주소가 10-bit offset이랑 6-bit page#가 됩니다. 32비트라면, 10-bit-offset과 22-bit page#가 됩니다. offset만 먼저 페이지 크기로부터 정하는 것입니다. 그래서 logical address로 physical address로 알아낸는 address traslation을 하는 방법은 페이지 번호를 보고, 이것에 해당하는 page table의 인덱스 번호로 갑니다. 1이므로 1번 인덱스 칸에 가보면, 000110이 들어가 있는데, 이것이 frame#입니다. 그 값을 그대로 앞으로 가져오고 offset을 그대로 가져와서 합치면, physical address가 됩니다. offset은 바뀌지 않고, page번호만 frame 번호로 바뀐 것입니다. 이런 식으로 paging에서는 address traslation을 진행합니다. 000110은 6이므로, 어떤 프로세스의 1번 페이지의 이 주소는 6번 메모리 프레임에 offset만큼 떨어진 것입니다.