[운영체제] Memory Management (2)

Hierarchical Paging

• Page table size 구하기 / 32bit address, 4KB page size

32bit CPU 혹은 OS; I/O단위가 32bit, 입출력이 32bit 단위로 => 32bit 주소체계

-> logical address space 최대 주소 2^32-1; 크기 = 2^32

-> page size 4KB(=2^12)

-> 2^32 / 2^12 = 2^20(=1 million) 개의 logical pages

-> 1 million 2^20 page table entries

-> 각 page table entry당 physical 주소 저장, 주소 체계가 32 비트니까 32비트 즉 4 Bytes 필요

-> 2^20마다 4 Bytes가 필요, 프로세스 당 page table size = 4 MB(2^22 Bytes)

-> 4MB page table 저장하려면 1 K(2^10)개의 page frames 필요

 

• 여기서 문제
  • 한 page table에는 1024개의 entries, 1025번째거는 그 다음 프레임에 들어감, 남의 프레임일 수 있음 <- paging 기법은 연속적이지 않아서

=> page table entry를 담고 있는 page frame 위치 찾은 후 접근 => Two-Level Page-Table Scheme

Two-Level Page-Table Scheme

Multilevel Paging and Performance

• 만약 바깥쪽 page table을 저장할 때도 하나의 page frame으로 충분하지 않다면? 또 찾기 위한 새로운 자료구조 필요
• 32비트에서는 4KB로 해결 가능, 2단계로 끝남
• 64비트 주소 체계를 사용하면? 다단계 필요 => 접근 단계가 많아져서 overhead 발생
• TLB hit rate이 높게 나와서 단계가 많아져도 괜찮음
• 그럼에도 64 비트 주소 체계에서 6 level 이 필요하니까 48 비트만 주소 체계로 사용하자 -> 4 levels

Hashed Page Tables

• 주소변환도 일종의 search structure 로 볼 수 있음
• collision 발생 시 O(n)까지 늘어날 수 있기 때문에 설계 잘해야 함
• 32비트까지는 2단계로 끝, Hash 필요 없음
• 일단은 32비트 주소체계보다 클 때 고려
• 해시 키 = logical page number

Inverted Page Table

• 프로세스마다 자기의 page table 가짐, 32비트의 경우 page table 크기가 4MB
• logical address는 32비트 주소체계의 경우 2^32-1번지까지 모두 사용 <- 하나의 프로세스가 저렇게 다 쓰는 경우는 없음
• logical -> physical이 아니라 physical -> logical로 하자, physical 크기는 정해져 있으니까
• 전에는 사용하지 않는 entry가 많았는데 거꾸로 하면 사용하는 페이지에 대한 주소만 들어감
• 그래서 프로세스마다 page table이 필요하지 않아짐

• logical page 번호와 pid를 가지고 physical frame의 위치를 찾아 내려온 거리(i)로 알아냄
• 원래 페이징 기법의 경우 바로 찾을 수 있었는데 inverted 에서는 i를 찾으려면 위에서부터 pid, p를 매칭해야됨 -> 좀 걸림
• => hash나 TLB를 사용해 해결할 수 있음
• page sharing이 불가능해진다는 엄청 큰 단점이 생김 <- page table에 pid, p가 공유되는 만큼 써져야 돼서
• 실제로 잘 사용되지 않음

Segmentation

• 단순히 크기만 가지고 page, frame으로 잘라 버려서 의미를 잃어버리게 됨
• segment 단위로 자르면 의미는 챙기고 크기는 각각 달라짐
• main() 한 덩어리, 함수 한 덩어리, 스택 덩어리 이런 식
• segment 끼리는 연속적으로 메모리에 올리자
• Logical address 구조: segment 번호 / offset
• Segment table
  • base: 각 segment의 시작 주소
  • limit: segment 길이
• Segment-table base register, STBR: segment table 위치
• Segment-table length register, STLR: segment table 길이, segment 개수

Segmentation 특징

•  Protection
  • paging에서는 사용되면 valid, 안 사용되면 invalid
  • segment table 크기 미리 정해야 되는데 사용 안 되면 valid bit로 표시할 수 있음
  • 의미 단위로 구현했기 때문에 Read/Write/eXecute 권한에 대해서도 표시할 수 있음
• Sharing
  • segment 단위 공유 가능해짐
• Allocation
  • 비어 있는 공간 중 어디에 올려야 되나? 사이즈가 다 다르니까 문제임
  • first fit? best fit?
  • external fragmentation 문제 생김; 공간이 너무 작아서 어디에 할당해야 할지 모르는
  • internal fragmentation 문제는 안 생김; segment 크기에 맞도록 할당하니까 할당 후 사용하지 않는 공간은 없음

Segmentation with Paging

• 짜투리 공간이 생기는 external fragmentation 문제를 해결하기 위함
• DRAM을 paging 기법처럼 frame 단위로 자름
• logical address space는 segment 단위로 자름
• 각각의 page는 segment 단위로 자름
• "각 데이터는 어떤 segment의 몇번째 page의 어떤 offset에 속해있다"

• segment table에는 원래 base address, limit이 있음
• 이거는 base address에다 offset 더해서 찾는 게 아니라 base address 가 의미 없음 -> segment마다 page table이 필요하니까 page table의 base address가 들어감

• external fragmentation 해결, internal fragmentation 생겨버림 -> paging과 같은 공간 효율성

segmentation with paging (feat. TLB)

 

 

한양대학교 강수용 교수님 운영체제 강의 내용 정리