목차
Paging
dynamic partition 방법을 복습해보자.
해당 방법의 문제점은 external fragmentation으로, 프로세스에 속하지 않는 작은 빈 메모리 조각이 생기는 점이었다.
위 마지막 그림을 보면 6, 6, 4MB의 빈공간 3개가 있는데, 다 합치면 16MB이지만 조각나있는 상태이기 때문에 예를 들면 10MB짜리 프로세스가 새로 생성되어도 들어갈 공간이 없다.
이런 문제를 해결하기 위해 compaction이라는 프로세스를 전부 이동시켜서 빈 메모리를 한곳으로 모으는 방법을 사용할 수 있는데, 이것도 시간이 걸리기 때문에 좋은 방법은 아니다.
compaction을 사용하지 않고도 흩어진 fragment들을 사용할 수 있도록 한 방법이 paging이다.
Paging에서는 page라고 부르는 일정한 크기의 조각으로 프로세스를 조각낸다.
이후 메인메모리 자체도 page frame 혹은 그냥 frame이라고 부르는 조각으로 분할한다.
이후 이 조각 단위로 메모리에 가져다 넣자는 것이 paging의 핵심이다.
page의 크기는 4KB이다. 디스크의 블록 하나 크기도 4KB인데, 블록 크기와 페이지 크기와 프레임 크기를 모두 통일시켜야 효율적이기 때문에 이와 같이 설정한다.
이처럼 4KB짜리로 나누는 방법은 고정 분할식 메모리 할당 개념을 계승했다고 볼 수 있다.
고정 분할식 메모리 할당 방법은 일정한 크기로 나누어진 메모리에 프로세스를 통째로 집어 넣는 방법이지만,
paging은 하나의 프로세스가 여러개의 page로 나뉘어 메모리에 들어간다는 차이점이 있다.
프로세스를 page 단위로 자르면 이 page 조각들을 식별해야하기 때문에, page마다 번호를 붙여야 한다.
각 프로세스 a, b를 page단위로 나누고, 각각 page들에 0번부터 번호를 부여한다.
이후 프로세스가 로드된 모습을 보면, 위 오른쪽 그림은 메모리 프레임 0번에 a 프로세스의 0번 page가 들어있다는 것을 나타내고, 다른 채워진 페이지 프레임들도 비슷하게 표현되어있다.
가장 왼쪽 그림을 보면, 프로세스 a, b, c가 페이지 조각들로 나뉘어 메모리에 들어있는 모습이다.
물론 메모리 이전 시작부분에 운영체제가 들어가는데 생략한 것이다.
여기서 b 프로세스가 종료되었다고 하자.
b 프로세스가 차지하고 있떤 메모리 전부를 운영체제가 회수하면 가운데 그림과 같이 4, 5, 6번은 빈 메모리 프레임으로 바뀐다.
이 상태에서 총 5개의 페이지로 구성된 프로세스 d가 실행되었다고 하자.
이전의 다이나믹 파티셔닝 방법을 사용한다면 프로세스 d가 들어갈 자리가 없었을것이지만,
paging 방법에서는 오른쪽 그림과 같이 다섯개의 페이지중 세개를 위에 넣고 나머지 두개를 아래 남는 자리에 흩어 넣는 방식으로 메모리에 배치할 수 있다.
물론 가운데 그림에서 compaction으로 프로세스 c를 위로 올리는 방법이 있지만, 이는 시간이 오래걸리기 때문에 paging 방법을 사용해서 충분히 연이어진 공간 없이도 큰 프로세스를 메모리에 배치할 수 있다.
이렇게 되면 프로세스를 빈 공간 아무곳에 빨리 넣고 실행 가능하므로 프로그램이 빨리 실행될 수 있다는 장점이 있고, external fragmentation 문제가 생기지 않는다는 장점이 있어 메모리를 더 효율적으로 사용할 수 있다.
하지만 대신 internal fragmentation 문제가 생긴다. 예를 들어 프로세스 c를 보면 4개의 페이지 프레임을 할당받았는데, 페이지 프레임 하나에 4KB이기 때문에 프로세스가 13, 14, 15KB인 경우에는 내부에 fragment가 생길 수 있다. 하지만 이 내부 fragment는 크기가 크지 않기 때문에 무시할 수 있다.
또한 오버헤드가 발생하는 단점이 있다.
프로세스 d는 현재 4,5,6,11,12 페이지프레임에 저장되어 있다.
프로그램이 실행되기 위해서는 이 페이지들이 연속적으로 서로 엑세스할 수 있어야한다.
예를 들어 d.2 실행 후 c.0가 실행되면 안되는것이다. 그렇게 되면 세그멘테이션 폴트로 허용되지 않는 메모리로 가는 문제가 된다.
때문에 d0, d1, d2, d3, d4가 연속적인것으로 보여지도록 해야한다.
이는 page table을 사용하면 가능해진다.
📁 Page table
page table은 운영체제가 프로세스마다 하나씩 만든다.
즉 프로세스에 의존적인 고유한 정보이므로 PCB에 저장된다.
위 그림은 프로세스 a, b, c, d에 대한 페이지 테이블이다.
프로세스 a의 페이지테이블을 보면 메모리 프레임 0, 1, 2, 3번에 페이지 0, 1, 2, 3번이 들어있다는 것을 나타내고 있다.
즉 페이지 테이블의 왼쪽 숫자가 페이지 넘버이고, 안에 들어있는 숫자가 프레임 넘버이다.
이때 페이지 넘버는 칸수를 나타내는 인덱스 번호이기 때문에 저장되는 정보가 아니다.
오른쪽 테이블은 프리 프레임 리스트로, 메모리 프레임 중 비어있는 것들을 관리한다.
이 프리 프레임 리스트는 슈퍼블록에 저장되는 정보이며, 이런식으로 프레임 번호들만 저장된다.
또 프로세스 b의 페이지 테이블을 보면 null이 들어있는데, 이는 메모리 프레임에 없다는 뜻이다.
하지만 지금 프로세스 b는 실행이 되었기 때문에 프로세스인것이므로 끝나서 없어진건 아니다. 만약 완전히 끝났다면 페이지 테이블도 지워진다.
이는 지금 프로세스 b가 보조기억장치에 있는 가상 주소 공간으로 swap out된 suspended 상태임을 말한다.
다이나믹 파티셔닝에서는 빈 메모리를 관리할 때, 일일이 빈 공간들의 시작주소와 끝주소를 저장하는 긴 테이블을 유지했어야 하기 때문에 찾는데도 시간이 오래 걸리는데,
paging 방법에서는 메모리 프레임 번호만 알고 있으면 되기 때문에 빈 메모리를 찾는데 시간이 짧게 걸린다.
이와 같이 paging 방법을 쓰면 page table을 갖고 있어야 한다는 단점이 있고,
메모리의 주소가 두 부분으로 구성된다는 특징이 있다.
즉 paging 방법을 쓰면 logical address가 페이지 번호와 페이지 내의 offset으로 바뀌어야한다.
여기서 offset이란 한 페이지 안에서의 위치를 말한다.
예를 들어 4KB짜리 페이지가 있다고 하면, 페이지 내에서 시작 주소는 0바이트, 끝 주소는 495바이트일것이다.
위 그림을 보자.
왼쪽 상단의 relateive address = 1502가 페이징을 쓰기 전 프로세스의 상대적 주소이다. 즉 프로세스의 시작으로부터 1502byte만큼 떨어져 있는 위치이다.
오른쪽 그림은 페이징을 사용하는 컴퓨터에서의 주소 체계이다.
페이지의 크기가 1KB = 1024byte라고 가정하자.
이 프로세스를 페이지단위, 즉 1KB 단위로 조각낸 상태인데, 지금 프로세스는 2KB보다 크기 때문에 세개의 페이지로 조각이 난 상태이다.
이때 세번째 페이지 프레임 안에는 사용되지 않는 부분, internal fragment가 있다.
paging 방법을 사용하든 사용하지 않든, 엑세스하려는 위치는 빨간 점선 부분으로 똑같은 위치이어야 한다.
즉 paging 방법을 적용하였다면, 적용하지 않은 것과 같은 위치에 접근하기 위해서 page 내에서의 위치를 알아야하는 것이다.
이를 위해 기존의 logical address의 바이너리 주소를 페이지 넘버와 페이지 오프셋으로 분할한다.
이때 페이지 크기가 1024byte, 즉 2의 10제곱이므로 오른쪽에서 10개의 비트가 페이지안에서 몇번째 byte 위치인지를 나타내고, 나머지 부분이 page 넘버를 나타낸다. 현재 위 그림에서는 page 1의 위치에 있으므로 page number부분 값이 1이다. 또한 logical address가 1502이고, 여기서 1024를 빼는 효과가 오른쪽 10개의 비트를 취하는 작업이며, 결과적으로 페이지 offset은 478이 된다.
예를 들어 8bit 컴퓨터를 생각해보자.
이는 주소를 8bit로 나타낸다는 의미이다.
이때 페이지 크기를 16byte로 가정하면, 이는 2의 4제곱이므로 8비트 주소에서 뒤 4자리가 page offset이 되고, 나머지가 page number를 나타낸다.
paging 방법에서의 주소를 실제로 어떻게 사용할까?
예를 들어 16bit 컴퓨터를 가정하자.
페이지 크기가 1KB이므로 logical address가 1502일때, page offset이 아래 10비트이므로, 나머지 6비트가 page number가 된다.
이것은 logical address이므로 이것으로부터 physical address를 알아내야한다.
먼저 page number를 보고 해당하는 페이지 테이블의 인덱스에 찾아간다.
위 그림에서 페이지 번호는 1번이므로 page table에서 인덱스 1칸 값에 가보면 000 110값이 있는데, 이것이 페이지 프레임 번호이다.
이 값을 그대로 가져오고, 뒤에 logical address의 offset을 합치면 physical address가 된다.
즉 offset은 바뀌지 않는다는 특징이 있다.
