Non-Countinous Memory Allocation / 가상메모리
사용자 프로그램을 여러개의 block으로 분할하고
실행 시 필요한 block들만 메모리에 적재한다.
나머지 block들은 swap device(Disk)에 존재한다.
기법들
Paging system
Segmentation system
Hybrid Paging/Segmentation system
프로그램을 작성할 땐 연속적인 메모리 할당을 가정한 주소를 사용한다.(논리 주소)
이것을 실제 주소로 변환하는 과정이 Address mapping이다.
따라서 사용자/프로세스는 실행프로그램 전체가 메모리에 연속적으로 적재되었다고
가정하고 실행가능하며 이는 강력한 장점이 된다.
Block Mapping
간단한 Address Mapping 기법.
사용자 프로그램을 block단위로 분할/관리하며 각 block에 대한 adress mapping정보를 유지한다.
이 시스템에서 가상주소는 v=(b,d)형태로 구성되어 있다.
b=block number(블록 번호)
d=displacement(offset) in a block(블록의 시작부분부터 얼마만큼 떨어져 있는가)
Block map table(BMT)를 통하여 Adress mapping정보를 관리한다.
커널 공간에 프로세스마다 BMT를 가진다
BMT의 구성
실제로 블록을 찾으려고 할 때, 다음과 같은 과정을 거친다.
b번 블록이 필요할 때, BMT에 접근하여 b에 대한 정보를 찾는다.
b가 만약 메모리에 이미 올라와 있다면(resident bit == 1) b의 실제 주소를 BMT에서 읽는다.
이 실제주소를 displacement와 더하여 실제 메모리 주소를 얻는다.
b가 메모리에 올라와있지 않다면(resident bit == 0) swap device에서 해당 블록을 메모리에 가져오고
BMT를 업데이트 한 후 나머지 단계를 수행한다.
Paging System
프로그램을 같은 크기의 블록으로 분할.
페이징 시스템에선 블록을 Page라고 부른다.
메모리의 분할영역인 Page frame은 Page와 크기가 같다
Windows가 실제로 사용하는 시스템이다(보통 windows의 페이지 크기는 4kb)
페이지들은 Swap device(가상 메모리)에 적재되며, 필요할 때 필요한 페이지를 메인메모리에 적재한다.
페이징 시스템의 특징
논리적 분할이 아닌, 크기에 따른 분할이다.
따라서 Segmentation System 대비 페이지 공유(Sharing) 혹은 보호 과정이 복잡하다
Segmentation System 대비 단순하고 관리하기 편해 효율적인 시스템이다
외부단편화를 방지하지만, 내부단편화가 발생할 수 있다.
why? 일정한 크기로 page를 나누므로, 마지막 page의 크기가 작아질 수 있고, 이는 곧 내부단편화이므로
페이징 시스템의 Address Mapping
Block Mapping과 거의 유사하다.
논리 주소는 v = (p,d) p=pages, d=displacement(offset)
Address Mapping 정보는 PMT(Page Map Table)을 사용한다.(BMT와 거의 유사)
Secondary Storage address는 swap device의 어디에 이 페이지가 저장되어 있는지 기록하는 주소이다.
Address mapping mechanism
Direct mapping(직접 사상)
Associative mapping(연관사상)
Hybrid direct/associative mapping)
Direct mapping
Block mapping방법과 유사하다.
page size: 페이지의 크기
entry size: PMT의 한 요소를 저장하는 요소의 크기(테이블 한칸 메모리 크기)
-
PMT에서 원하는 요소에 접근하기 위해, PMT의 시작부분 + 페이지 숫자 * entrySize를 통해
내가 필요한 페이지의 정보가 PMT 어디에 있는지 찾는다. -
PMT에 저장된 정보를 사용하여 그 페이지가 메인메모리 어디에 저장되어 있는지 얻는다.
-
만약 그 페이지가 메인메모리에 올라와있지 않다면(page fault)
메모리에 올리고 PMT를 업데이트, 이후 2번과정을 수행한다.
page fault
page fault가 발생하여 swap device에 저장된 페이지를 가져와 적재하는 과정에서
Context switching이 발생하므로 오버헤드가 크다
따라서 가급적 줄여야 한다.
메모리 매핑 과정에서 메모리를 2번 접근하므로,
메모리 접근 횟수가 2배가 되어 성능이 저하되고, PMT를 위한 메모리 공간이 필요한 단점이 있다.
이를 해결하기 위한 방안
메모리 접근횟수 문제 해결: Associative mapping(TLB)
PMT 공간필요 문제 해결:
PMT를 위한 전용 기억장치 사용(Dedicated register or cache memory)
Hierarchical paging
Hashed page table
Inverted page table
Associative mapping
Translation Look aside Buffer(TLB)에 PMT를 적재하여
메모리 접근횟수가 2배라는 Direct Mapping의 단점을 해소한다.
(위의 Direct mapping방식은 PMT를 커널에 적재한다고 가정한 상태)
TLB는 하드웨어로 구현하여 PMT를 병렬탐색(Parallel search) 가능
따라서 address mapping을 빠르게 수행할 수 있어 오버헤드가 적고 속도가 빠르다
하지만 하드웨어가 비싸서 큰 PMT를 다루기 어렵다는 한계가 있다.
Hybrid Paging/Associative mapping
direct mapping과 Associative mapping를 혼합하여 사용
why? HW가격을 줄이고, Associative의 장점을 활용
작은 크기의 TLB를 사용하여
PMT는 커널 공간에 저장하고, PMT의 일부 entry들만 TLB에 적재한다
최근 사용된 page들에 대해 entry를 저장한다
why? 한번 접근한 영역을 다시 접근 혹은 인접영역을 접근하는 특성(지역성) like 캐시
Associative mapping의 과정에서,
필요한 페이지의 entry가 TLB에 적재되어 있는지 확인하는 과정이 추가된다.
없다면 PMT에 접근하여 필요한 entry를 TLB에 올리는 과정을 수행한 후 나머지 작업을 수행한다.
페이징 시스템의 메모리 관리
페이징 시스템에선 메모리를 Page와 같은 크기로 미리 분할하여 관리 / 사용한다.
이렇게 잘라둔 한 메모리 영역을 Page frame이라 하고, FPM(고정파티션)기법과 유사하다.
Frame table
이렇게 잘라둔 page frame을 관리하기 위한 자료구조이다.
page frame당 하나의 entry를 가지게 된다.
구성
1. Allocated/available field: 할당되었는지, 혹은 사용가능한지 표기
2. PID field: 어떤 페이지가 올라와 있는지 표기
3. Link field : 사용가능 한 fp들을 연결
4. AV: free list의 시작점
페이지 번호와(page frame number)
이 페이지를 사용하고 있는지 여부(allocated),
사용하고 있다면 누가 사용하고 있는지(PID)를 표기한다.
Link는 비어있는 다음 페이지 프레임을 링크드 리스트처럼 연결한다.
AV는 비어있는 첫번째 페이지 프레임을 표기한다.
만약 AV가 지칭하고 있는 페이지 프레임이 할당되었다면,
Link를 타고 흘러가 다음 비어있는 페이지 프레임을 가리키게 된다.
Page Sharing
여러 프로세스가 특정 Page를 공유 가능한 개념
여러 프로세스가 특정 page에 담긴 함수를 사용한다고 가정했을 때,
프로세스마다 그 page를 할당하는 것보단, 하나의 페이지를 공유해서 사용하여 낭비를 줄인다.
Non Continuous allocation이기에 활용 가능한 기능이다.
공유 가능한 Page로는
1. Procedure Pages: 퓨어 코드를 담고 있는 페이지
2. Data Pages: 데이터만 담고 있는 페이지
둘 다 가능하지만, Data Pages의 경우 Read only data의 경우 문제없이 공유가 가능하지만
Write도 가능한 data의 경우 병행성 제어 기법 관리 하에서만 가능하다
다음과 같이 한 프로그램을 프로세스 3개가 사용하고, 모두 ed1, ed2, ed3 세 페이지를 사용한다고 했을때
각각의 프로세스의 페이지 테이블에 ed1,ed2,ed3을 담고 있는 3번 4번 6번을 사용하겠다고 기입하여 사용한다.
실제 작성하는 데이터는 서로 다른곳에 기록한다.(1,2,7번 메모리 페이지)
Data Pages 공유 예)
프로세스마다 각각의 PMT(Page Manage Table)을 가지고 있지만,
접근하는 페이지 주소는 같으니 그 페이지를 공유하여 사용할 수 있다.
Procedure Pages 공유 예)
Procedure pages 공유에서는 문제가 발생할 수 있다.
Procedure(함수)내에서 다른 곳으로 이동하는 분기branch가 존재한다고 했을 때
이 Procedure을 사용하는 프로세스의 PMT에 저장된 Procedure의 Page num이 다르다면
같은 양만큼 이동해도 다른 결과를 초래할 수 있다.
이를 해결하기 위해 같은 Procedure을 가리킨다면 시작주소(page num)을 통일하도록 약속한다.
즉 프로세스들이 shared page에 대한 정보를 PMT의 같은 entry에 저장하도록 한다.
Page Protection
여러 프로세스가 같은 page를 공유할 때 보안 문제가 발생할 수 있다.
이를 해결하기 위해 Protection bit를 사용한다.
페이지 테이블에 각 페이지에 접근한 프로세스가 할 수 있는 행위를 기입해 둔다
페이징 시스템은 고정된 크기의 블록으로 미리 잘라두었기 때문에 외부 단편화는 존재하지 않지만 내부 단편화는 존재한다.
페이징 시스템은 메모리의 효율적 활용이 가능하지만 프로그램의 논리적 구조를 고려하지 않는다.
즉 페이지를 그저 크기에 따라 잘라두었기 때문에 functionA가 존재할 때,
같은 함수가 여러 조각으로 찢어져 있을 수 있다.
이때문에 Page sharing과 protection이 복잡하다.
이와 같은 부분에서 장점을 가지는 시스템이 Segmentation System이다.
Segmentation System
논리가 아닌 크기로 자른 Page System의 단점을 해결하기 위해
크기가 아닌 논리 단위로 자른 시스템
프로그램을 논리적 block으로 분할한다(Segment)
Block의 크기가 서로 다를 수 있다. ex) stack, heap, main procedure...
세그먼테이션 시스템의 특징
Variable Partition Memory처럼 메모리를 미리 분할하지 않는다
세그먼트 공유 및 보호가 용이하다
Address mapping 및 메모리 관리의 overhead가 크다
내부단편화는 존재하지 않지만 외부단편화는 존재한다(paging과 반대)
세그먼테이션의 Address mapping
가상주소를 v = (s, d)로 표현한다.
s는 segment, d는 displavement(offset) in segment이다.
페이징의 PMT처럼 Segment Map table(SMT)를 사용한다
대체로 페이싱 시스템과 유사하다.
SMT
PMT와 유사하지만, segment length와 protection bits가 추가되었다.
각 세그먼트의 길이가 다르므로 segment length에 세그먼트의 길이를 기록하고,
각 세그먼트에 대해 프로세스가 사용 가능한 권한을 protection bits에 기록한다.
Address mapping
블록 매핑, 페이징 매핑과 동일하다.
1. 프로세스의 SMT에 저장되어 있는 주소 b에 접근
2. SMT에서 세그먼트s의 entry를 찾는다.
-s의 entry위치 = b + s * entrySize
3. 찾아진 Entry에 대해 다음 단계들을 순차적으로 실행
-
존재 비트가 0인경우 segment fault.
swap devece로부터 해당 segment를 메모리로 적재 한 후 SMT를 갱신 -
변위(d)가 segment길이보다 큰 경우(d > ls)
즉 세그먼트를 초과하는 곳에 접근하려고 할 경우
segment overflow exception처리 모듈을 호출 -
protection bit를 검사하여 허가되지 않은 연산일 경우
segment protection exception처리 모듈을 호출
4. 실제 주소 r 계산(r = as + d)
5. r로 메모리에 접근
Memory Management
세그먼테이션 시스템의 메모리 관리는 VPM과 유사하다.
세그먼트 적재 시 크기에 맞추어 메인 메모리를 분할한 후 적재한다.
Segment Sharing / Protection
논리적으로 분할되어 있어 공유 및 보호가 용이하다
페이징 시스템에서 분기점 관련 문제가 없다.
세그먼테이션 시스템 정리
Hybrid Paging/Segmentation System
장단점이 명확한 Paging과 Segmentation의 장점만을 취하기 위한 방법
1. 프로그램은 논리 단위의 segment로 분할하고
2. 각 segment를 고정된 크기의 page들로 분할한다.
Address mapping
가상주소 v = (s,p,d) 와 같이 표기한다.
s : segment number
p : page number
d : offset in a page
SMT와 PMT를 모두 사용한다.
각 프로세스마다 하나의 SMT가 존재하고
각 Segment마다 하나의 PMT가 존재한다.
Address mapping은 Direct, associated 등을 사용하며
메모리 관리는 FPM(Fixed Partition Memory)와 유사하다
(실제로 메모리에 올라가는 단위는 Page이므로)
SMT in hybrid mechanism
일반 SMT와 비교하면 이 segment가 메모리에 올라와 있는지를 표기하는
residence bit가 없다는것이 차이점이다.
why? segment가 메모리에 직접 올라가는것이 아니기 때문
대신 PMT가 어디 있는지 표기하는 PMT address라는 필드가 추가된다.
PMT for a segment k in hybrid mechanism
page가 메모리에 올라가므로 residence bit가 존재한다.
Address mapping tables
프로세스마다 1개 존재하는 SMT에서 각 세그먼트를 찾고,
SMT를 타고 들어와 세그먼트마다 1개 존재하는 PMT에서 페이지를 찾는다.
Direct mapping in hybrid mechanism
1. SMT 시작주소 b에 세그먼트 넘버 x SMT 엔트리 사이즈를 더해 원하는 세그먼트를 찾아간다.
2. 찾은 세그먼트 시작주소 bs에 페이지 넘버 x PMT 엔트리 사이즈를 더해 원하는 페이지를 찾아간다
3. 찾은 페이지 엔트리에서 residence bit를 검사하여 메모리에 적재되어 있으면
메인 메모리에 적재된 페이지 프레임의 번호를 알 수 있다
4. 찾은 페이지 프레임 * 페이지 사이즈를 한 수 displacement를 더하여 찾는다.
이와 같은 과정 속에서 메모리 접근을 총 3번 하게된다.(SMT, PMT, main memory)
당연히 overhead가 커지지만, 이 단점보다 장점이 크므로 이와 같은 방법을 사용한다.
Hybrid Paging/Segmentation System 정리
외부 단편화는 없지만 내부 단편화는 발생 가능하다.
전체 테이블 수가 증가함에 따라 메모리 소모가 크고, address mapping 과정이 복잡하다.
메모리 접근이 3배 증가하므로 성능이 저하될 수 있다.
