페이지 테이블 구현
개념적인 페이지 테이블이 어떻게 동작할까 생각하며 구현하였습니다. 완벽히 개념과 일치하지는 않지만 어떤식으로 가상 주소가 물리주소로 맵핑 되는지에 대한 흐름을 이해 할 수 있을거라 생각합니다.(?)
클래스
MainMemory
public class MainMemory {
private final byte[] data = new byte[Main.memorySize];
// 1바이트 크기 식 메모리 생성
public MainMemory() {
Random random = new Random(System.currentTimeMillis());
random.nextBytes(data);
}
public int load(int physicalAddress) {
return data[physicalAddress];
}
}먼저 메인 메모리입니다. 간단하게 메모리 구조만 나타냈습니다. Byte 배열을 이용하였으며 배열의 인덱스가 주소이름이라고 할 수 있습니다.
MainMemory()
생성과 동시에 바이트 배열에 랜덤한 값을 생성합니다.
load(int physicalAddress)
특정 주소의 값을 반환합니다.
MMU (Memory Management Unit)
public class MMU {
public int logicalAddressToPhysicalAddress(PageTable pageTable, int logicalAddress) throws RuntimeException {
int pageNum = logicalAddress & (Integer.MAX_VALUE << pageTable.getOffSetLength());
int offSet = logicalAddress & (Integer.MAX_VALUE >> pageTable.getPageLength());
System.out.println("페이지 시작 주소 : " + Integer.toHexString(pageNum));
System.out.println("offSet : " + offSet);
int frameNum = pageTable.getFrame(pageNum);
System.out.println("맵핑된 프레임 시작 주소 : " + Integer.toHexString(frameNum));
if (offSet >= Main.frameSize) {
throw new RuntimeException();
}
return frameNum | offSet;
}
}논리 주소를 물리주소로 맵핑 하는 역할을 합니다.
int logicalAddressToPhysicalAddress(PageTable pageTable, int logicalAddress)
프로세스의 페이지 테이블과 논리주소를 통해 물리주소로 맵핑하는 함수 입니다.
페이지 번호는 오프셋을 표현하는 범위를 제외하고 마스킹한 값입니다.
오프셋 번호는 페이지를 표현하는 범위를 제외하고 마스킹한 값입니다.
이후 페이지 테이블에서 맵핑 된 frame 주소를 가져온 후 메모리 범위를 체크합니다.
메모리 범위를 벗어나지 않는다면 frame 주소와 offset주소를 더한 후 반환합니다.
FrameTable
프레임 테이블입니다. 해당 프레임이 할당 돼 있는지 확인하며 각 프로세스에게 페이지 테이블을 할당합니다.
public class FrameTable {
public static class FrameTableEntry {
private final int relocationRegister;
private boolean isValid;
public FrameTableEntry(int relocationRegister, boolean isValid) {
this.relocationRegister = relocationRegister;
this.isValid = isValid;
}
public int getRelocationRegister() {
return relocationRegister;
}
public void setValid(boolean valid) {
isValid = valid;
}
}
private final List<FrameTableEntry> frameTable = new ArrayList<>();
public FrameTable() {
for (int i = 0; i < Main.memorySize; i += Main.frameSize) {
frameTable.add(new FrameTableEntry(i, false));
}
}
public PageTable allocatePageTable(Process process) {
List<FrameTableEntry> entriesOfCanAllocateFrame = frameTable.stream()
.filter(entry -> !entry.isValid)
.collect(Collectors.toList());
// 랜덤한 위치를 만들기 위해
Collections.shuffle(entriesOfCanAllocateFrame);
// 가능한 프레임보다 페이지가 크면 에러 반환
if (entriesOfCanAllocateFrame.size() < process.calcNumOfPages())
throw new RuntimeException();
return new PageTable(process.getSize(), entriesOfCanAllocateFrame);
}
}FrameTableEntry Class
페이지 테이블 엔트리입니다. 해당 프레임의 base 주소를 가지고 있으며 해당 프레임의 할당 유무를 확인합니다.
FrameTable()
메모리 크기와 프레임 크기를 통해 프레임 테이블을 생성합니다.
allocatePageTable(long processSize)
할당되지 않은 페이지 테이블 엔트리를 구한 후 페이지 테이블을 생성합니다.
PageTable
public class PageTable {
private final Map<Integer, Integer> tables = new HashMap<>();
private final int pageLength;
private final int offSetLength;
public int getPageLength() {
return pageLength;
}
public int getOffSetLength() {
return offSetLength;
}
public PageTable(int processSize, List<FrameTable.FrameTableEntry> entriesOfCanAllocateFrame) {
pageLength = (int) (Math.log(Main.memorySize / Main.frameSize) / Math.log(2));
offSetLength = Main.busSize * 8 - pageLength;
for (int i = 0, id = 0; i < processSize; i += Main.frameSize, ++id) {
FrameTable.FrameTableEntry frameTableEntry = entriesOfCanAllocateFrame.get(id);
frameTableEntry.setValid(true);
int pageNum = i << offSetLength;
int frameNum = frameTableEntry.getRelocationRegister();
tables.put(pageNum, frameNum);
}
}
public int getFrame(int pageNum) {
return tables.get(pageNum);
}
protected int tableSize() {
return tables.size();
}
protected List<Integer> getTables() {
return new ArrayList<>(tables.keySet());
}
}페이지 테이블 입니다. 페이지와 프레임을 연결합니다.
PageTable()
pageLength는 페이지 번호를 표현할 수 있는 비트 수 입니다. 메모리 크기와 프레임 크기를 통해 계산합니다.
offSetLength는 프레임 크기입니다. 프레임이 16Byte이고 메모리 번지를 1Byte식 표현한다면 16개의 오프셋을 가질 수 있습니다.
페이지 테이블을 생성합니다. 할당 가능한 프레임을 페이지와 맵핑합니다.
int getFrame(int pageNum)
페이지에 할당된 프레임을 반환합니다.
Process
private final int size;
private final PageTable pageTable;
public Process(int size) {
this.size = size;
pageTable = Main.frameTable.allocatePageTable(this);
}
public PageTable getPageTable() {
return pageTable;
}
public int getLogicalAddress() {
Random random = new Random();
List<Integer> pageNums = pageTable.getTables();
int pageNum = pageNums.get(random.nextInt(pageTable.tableSize()));
// offSet 범위 초과를 위해 +5
int offSet = random.nextInt(Main.frameSize + 5);
return pageNum | offSet;
}
public int getSize() {
return size;
}
public int calcNumOfPages() {
return (size / Main.frameSize) + (size % Main.frameSize == 0 ? 0 : 1);
}
}프로세스입니다. 프로세스의 크기를 가지며 각 프로세스는 페이지 테이블을 가지고 있습니다.
Process()
프로세스가 생성시 프레임 테이블에 페이지 테이블 할당을 요청합니다. (메모리 할당을 요청한다고 생각하면 됩니다.)
getLogicalAddress()
테스트를 위해 임의적으로 생성하는 논리 주소입니다.
Main
public class Main {
// 모두 Byte 크기
// 시스템 버스 크기 32bit = 4Byte
// 메모리 크기 256KB
// 프레임 크기 16Byte
static final int busSize = 1 << 2;
static final int memorySize = 1 << 18;
static final int frameSize = 1 << 4;
static MainMemory mainMemory = new MainMemory();
static MMU mmu = new MMU();
static FrameTable frameTable = new FrameTable();
public static void main(String[] args) {
final int processSize = 1 << 18;
Process process = new Process(processSize);
for (int i = 0; i < 10; ++i) {
System.out.println("---------------- Test Case " + i + " ----------------");
int logicalAddress = process.getLogicalAddress();
System.out.println("논리 주소 : " + Integer.toHexString(logicalAddress));
try {
int physicalAddress = mmu.logicalAddressToPhysicalAddress(process.getPageTable(), logicalAddress);
System.out.println("물리 주소 : " + Integer.toHexString(physicalAddress));
System.out.println("물리 주소 내 데이터 : " + mainMemory.load(physicalAddress));
} catch (RuntimeException e) {
System.out.println("범위를 벗어난 오프셋 입니다.");
}
}
}
}메인 함수입니다. 전체적인 흐름을 관리합니다.
- 메인 메모리를 생성합니다.
- 프레임 테이블을 생성합니다.
- MMU를 생성합니다.
(이미 메모리에 올려갔음을 표현하기 위에 정적변수로 선언하겠습니다.) - 프로세스를 생성합니다.
- 테스트를 진행합니다.
6.1. 프로세스에서 랜덤한 논리주소를 생성합니다.
6.2. mmu에게 논리주소를 물리주소로 변환하도록 요청합니다.
6.3. 결과에 맞게 출력 합니다.
출력 결과
---------------- Test Case 0 ----------------
논리 주소 : 74c00003
페이지 시작 주소 : 74c00000
offSet : 3
맵핑된 프레임 시작 주소 : 11c00
물리 주소 : 11c03
물리 주소 내 데이터 : -104
---------------- Test Case 1 ----------------
논리 주소 : cec00006
페이지 시작 주소 : cec00000
offSet : 6
맵핑된 프레임 시작 주소 : fd70
물리 주소 : fd76
물리 주소 내 데이터 : -110
---------------- Test Case 2 ----------------
논리 주소 : a8400008
페이지 시작 주소 : a8400000
offSet : 8
맵핑된 프레임 시작 주소 : 23150
물리 주소 : 23158
물리 주소 내 데이터 : 69
---------------- Test Case 3 ----------------
논리 주소 : 2bc0000e
페이지 시작 주소 : 2bc00000
offSet : 14
맵핑된 프레임 시작 주소 : 38e30
물리 주소 : 38e3e
물리 주소 내 데이터 : 9
---------------- Test Case 4 ----------------
논리 주소 : 73400005
페이지 시작 주소 : 73400000
offSet : 5
맵핑된 프레임 시작 주소 : 3fa40
물리 주소 : 3fa45
물리 주소 내 데이터 : 2
---------------- Test Case 5 ----------------
논리 주소 : a8800009
페이지 시작 주소 : a8800000
offSet : 9
맵핑된 프레임 시작 주소 : 32ea0
물리 주소 : 32ea9
물리 주소 내 데이터 : 42
---------------- Test Case 6 ----------------
논리 주소 : a3c00013
페이지 시작 주소 : a3c00000
offSet : 19
맵핑된 프레임 시작 주소 : 19a60
범위를 벗어난 오프셋 입니다.
---------------- Test Case 7 ----------------
논리 주소 : 8b800000
페이지 시작 주소 : 8b800000
offSet : 0
맵핑된 프레임 시작 주소 : 1fb20
물리 주소 : 1fb20
물리 주소 내 데이터 : -128
---------------- Test Case 8 ----------------
논리 주소 : 73000005
페이지 시작 주소 : 73000000
offSet : 5
맵핑된 프레임 시작 주소 : 2e590
물리 주소 : 2e595
물리 주소 내 데이터 : -67
---------------- Test Case 9 ----------------
논리 주소 : c340000d
페이지 시작 주소 : c3400000
offSet : 13
맵핑된 프레임 시작 주소 : 158a0
물리 주소 : 158ad
물리 주소 내 데이터 : 71결론
완벽하게 가상주소를 물리주소로 맵핑하는 흐름은 아니지만 페이징 기법에 대한 충분한 이해는 가능하다고 생각합니다. 엄밀히 말하면 해시 페이지 테이블에 가깝습니다. (기본 페이징 기법이라면 page table base register 주소값에 바로 오프셋을 더한 주소를 접근하기 때문입니다.)
페이지 테이블, 프레임 테이블 모두 메인 메모리 상에 존재하기에 주소에 대해서 오프셋을 더하면서 바로 접근할 수 있지만 페이징의 흐름을 확실히 표현하기 위해 각각의 클래스로 나누어서 자료구조를 통해 값을 얻을 수 있도록 구현하였습니다.
페이징 기법이 개념적인 부분에서 햇갈리는 부분이 많았는데 실제로 유사하게 만들어보면서 이해하는데 많은 도움이 됐습니다.
.