Virtual Memory

Non-continuous allocation

• 연속되지 않게 올라가는 memory allocation 기법.

• 사용자 프로그램을 여러 개의 block으로 분할.

• 실행 시 필요한 block들만 메모리에 적재.

• 나머지 block들은 swap device에 존재.

• 우선 continuous allocation은 상대 주소를 0으로 가정하고 할당 후 상태주소를 재배치함.

• non-continuous allocation은 virtual address를 real address로 바꾸어줌.
• virtual address는 가상 주소 이며 연속된 메모리 할당을 가정한 주소임. 가정을 해야 나눠진 부분을 고려하지 않고 프로그램을 짤 수 있음.
• real address는 실제 주소로 실제 메모리에 적재된 주소임.

• 장점 ) 사용자, 프로세스는 실행 프로그램 전체가 메모리에 연속적으로 적재되었다고 가정하고 실행할 수 있음.

• 사용자 프로그램은 block 단위로 분할되고 관리됨. 그렇기에 각 block에 대한 address mapping 정보를 유지해야 할 필요가 있음.

• Virtual address : v = (b, d) → virtual address v는 b와 d로 구성되어 있음.
• b는 block의 번호.
• d는 시작부터 얼마만큼 떨어져 있는가 (offset)를 담고 있음.

• 이는 실제로 Block map table (BMT)를 통해 address mapping 정보를 관리함.
• kernel 공간에 프로세스마다 하나의 BMT를 가짐.

• 전체 프로세스는 swap device에 있고, 일부는 메모리에 올라가 있고, 일부는 올라가 있지 않음. 이때 올라갔는지 올라가지 않았는지는 residence bit로 기록함.
• residence bit : 해당 블록이 실제로 메모리에 올라갔는지 여부 (0 or 1).

• real address는 그렇게 올라간 메모리가 실제 어디에 저장되어 있는지를 기록함.

• 그렇다면 이제 어떻게 실제 주소를 찾아갈까?
• 이 시스템이 향후 얘기할 기법들의 기본임.

1. b가 의미하는 block number를 찾아 BMT에 메모리가 올라가 있는지 확인하기 위해 resident bit를 확인함.

2. 올라가 있다면 어디 올라가있는지에 대한 정보도 알 수 있음(real address).

3. a라는 시작점을 구한 후 d만큼 떨어진 곳을 구해 실제 주소를 찾아갈 수 있음.

기법들

• paging system

• segmentation system

• hybrid paging/segmentation system

paging system

• 프로그램을 같은 크기의 블록으로 분할 (pages)
• page : 프로그램 분할된 block.
• page frame : 메모리의 분할 영역, page와 같은 크기임.

• 특징 (segmentation 대비)
• 크기에 따라 일정하게 분할했기 때문에 논리적인 분할이 아님. ex) function 단위로 자르지 않고 function과 function 사이를 자르기도 함.
• page 공유 및 보호 과정이 복잡함.
• simple and efficient
• no external fragmentation.
• page에 따라 올라가고 안올라갈 뿐 메모리 공간이 남았는데 못올라가거나 그런 경우는 없음.
• 단, internal fragmentation (내부 단편화) 발생 가능.

• paging system의 address mapping
• virtual address : v = (p, d)
• p : page number
• d : offset
• PMT(Page Map Table) 사용. BMT와 유사함.



• mechanism
• Direct mapping





• block mapping과 유사함.
• PMT를 커널 안에 저장함.
• 문제점 : 메모리 접근 횟수가 2배라 성능 저하 문제와 PMT를 위한 메모리 공간 필요.
• 이에 대한 해결 책으로 associative mapping이 등장함 (PMT를 위한 전용 기억 장치 공간 제공).
• Associative mapping



• TLB, Translation Look-aside buffer에 PMT 적재. address mapping 시 옆에 두고 사용하는 특별한 장치라 생각하면 좋음.
• associative high-speed memory (전용 HW)
• 병렬로 검색하기 때문에 low overhead, high speed
• 하지만 크기가 작아 큰 PMT를 다루려면 비용이 많이 듦.
• 그래서 두 기법을 혼합해서 사용함.
• Hybrid direct/associative mapping
• 두 기법을 혼합하면 HW 비용은 줄이고, associative mapping의 장점 활용.
• 작은 크기의 TLB를 사용.
• PMT : 메모리(커널)에 저장.
• TLB : PMT 중 일부 entry들을 적재. 지역성을 활용하여 한번 접근한 영역은 다시 접근할 가능성이 높기 때문에 최근에 사용된 page들에 대한 entry 저장.

• memory management
• 메모리를 일정한 크기(page의 크기)로 미리 분할하여 관리, 사용함. (Fixed partition multiframe 기법과 유사)
• 잘라놓은 것을 관리하기 위해 frame table 형태로 데이터 구조를 사용함.
• frame table : page frame 당 하나의 entry



• 구성
• allocated/avaliable field : 사용 중인지
• PID field : 프로세스 ID
• Link field : 빈 entry에 대한 linked list
• AV : 가장 처음으로 비어있는 entry를 지칭하는 포인터

• page sharing
• page system에는 page sharing이라는 개념이 필요함.
• page sharing은 여러 프로세스가 특정 page를 공유 가능함. 똑같은 함수를 메모리에 따로 적재할 필요없이 하나에 올린 걸 여러 프로세스가 쓸 수 있도록 하는 것임. 이는 non-continuous allocation이라 가능.
• 공유 가능 page
• procedure pages
• pure code
• data pages
• read-only data
• read-write data (단 병행성 제어 기법 관리하에 사용 가능)





• 단 공유를 하기 때문에 protection을 필요로 함.



• 프로세스들이 공유하는 정보는 PMT에 같은 이름으로 저장함.
• 접근 권한을 관리하는 protection bit도 사용함.

segmentation system

• 프로그램을 논리적 block으로 분할.
• 이때 block을 segment라고 함.
• block의 크기가 서로 다를 수 있음.
• ex) stack, heap, main procedure, shared lib, etc

• 특징 (크기가 다르기 때문에 생기는 필연적인 것들임)
• 메모리를 미리 분할 하지 않음 (vpm과 유사).
• segment sharing/protection이 용이함.
• address mapping 및 메모리 관리의 overhaed가 큼.
• no internal fragmentation. 하지만 external fragmentation 발생 가능.

• segmentation system의 address mapping
• virtual address : v = (s, d)
• s : segment number
• d : offset
• Segment Map Table (SMT) 사용.
• address mapping 자제는 paging system과 유사한 address mapping mechanism을 가짐.

• memory menagement
• VPM과 유사. segment 적재 시 크기에 맞춰 분할 후 적재.

• 장점
• 필요한 segment만 메모리에 적재하여 사용 → 메모리의 효율적 활용.

• 단점
• segment mapping overhead
• 메모리 공간 및 추가적인 메모리 접근이 필요함.
• 전용 HW 활용으로 해결 가능.

hybrid paging/segmentation system

• 방법
1. 논리 단위의 segment로 분할 (SMT).
2. 각 segment를 고정된 크기의 page들로 분할 (PMT).
• 잘라놓고 page 단위로 메모리에 적재.

• address mapping
• Virtual address : v = (s, p, d)
• s : segment number
• p : page number
• d : offset in a page
• SMT와 PMT 모두 사용.
• 실제 메모리는 page가 올라감 → FPM과 유사. paging system과 유사하게 관리함.









• hybrid system은 두 개의 장점을 모두 취할 수 있는 반면 메모리 access를 3번한다는 문제를 가짐. 하지만 얻는 장점이 많아 사용함. 마찬가지로 특별한 HW를 통해 해결할 수 있음.

• 요약
• 논리적 분할(segment)과 고정 크기 분할(page)을 결합.
• page sharing/protection이 쉬움.
• 메모리 할당/관리 overhead가 작음.
• no external fragmentation. 내부 단편화는 발생 가능.
• 전체 테이블 수 증가.
• 메모리 소모가 큼.
• address mapping 과정이 복잡함.
• direct mapping의 경우, 메모리 접근이 3배. 성능이 저하될 수 있음.